题目描述

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

1. 将 $A_i$ 加上 $1$，代价为 $1$。
2. 将一个 $A_l=A_r$ 且 $l\not=r$ 的区间 $[l,r]$ 赋值为 $-10^9$，代价为区间长度。

注意，$A_l=A_r=-10^9$ 也可以进行操作二。

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

输入格式

本题有多组测试数据。

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

对于每组数据：

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

输出格式

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

2
3
1 3 2
9
1 2 3 4 5 6 7 8 9

4
13

提示

样例解释

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

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

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

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

1. 将 $A_1$ 和 $A_8$ 分别增加 $1$。
2. 将 $[1,2]$ 和 $[8,9]$ 赋值为 $-10^9$。
3. 将 $[2,8]$ 赋值为 $-10^9$。

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

数据范围

本题采用捆绑测试。

对于 $100\%$ 的测试数据，满足 $1\le T\le 10^2$，$2\le n,\sum n\le 10^6$，$1\le A_i\le n$。