P12675 「LAOI-8」Boundary
题目描述
给定一个长度为 $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$ 行，一行一个正整数，表示每组数据所需的最小代价。
说明/提示
### 样例解释
对于样例组 #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$，容易证明该方案最优。
### 数据范围
**本题采用捆绑测试。**
|子任务编号|$n,\sum n$|特殊性质|分值|
|:-:|:-:|:-:|:-:|
|$1$|$\le 12$|无|$10$|
|$2$|$\le 10^6$|$A$ 单调递增|$15$|
|$3$|$\le 5\times10^3$|无|$35$|
|$4$|$\le 10^6$|无|$40$|
对于 $100\%$ 的测试数据，满足 $1\le T\le 10^2$，$2\le n,\sum n\le 10^6$，$1\le A_i\le n$。