给定一个长度为 $n$ 的排列 $A$，即 $A$ 包含 $[1,n]$ 中的所有正整数，你可以进行两种操作：

1. 将Ai加上 $1$，代价为 $1$。
2. 将一个Al=Ar且 $l!=r$ 的区间 $[l,r]$ 赋值为 $-10^9$，代价为区间长度。

注意，Al=Ar=−10^9 也可以进行操作二。

问使得序列 $A$ 所有元素均变为 $-10^9$的最小代价。

本题有多组测试数据。

第一行给定一个正整数 $T$，表示数据组数。

对于每组数据：

第一行给定一个正整数 $n$，表示排列 $A$ 的长度。
第二行给定 $n$ 个正整数，表示排列 $A$。

共 $T$ 行，一行一个正整数，表示每组数据所需的最小代价。

样例解释

对于样例组 #1 的第一组测试数据，最小代价按如下操作得到：

1. 
   将A1增加 $1$。
   


2. 
   将 $[1,3]$ 赋值为 $-10^9$。
   

代价为 $1+3=4$，容易证明该方案最优。

对于样例组 #1 的第二组测试数据，最小代价按如下操作得到：

1. 
   将A1和 A8分别增加 $1$。
   


2. 
   将 $[1,2]$ 和 $[8,9]$ 赋值为 $-10^9$。
   


3. 
   将 $[2,8]$ 赋值为 $-10^9$。
   

代价为 $2+4+7=13$，容易证明该方案最优。

贪心