修线(modify)
题目描述
你请了一位师傅到你家修线。
有 $n$ 根线,第 $i$ 根线的长度为 $a_i$。每次操作你可以向师傅支付 $1$ 元,选择一个 $i(1\le i\le n)$,让师傅把第 $i$ 根线长度增加 $1$(即将 $a_i$ 的值增加 $1$)。你可以进行若干次这样的操作(不同的操作中选择的 $i$ 可以相同),使得对每根线 $i$,都存在另一根线 $j\neq i$,使得 $a_i=a_j$ 且不存在 $k\in [\min(i,j)+1,\max(i,j)-1],a_k\ge a_i$。你想知道为了达成目标,最少需要向师傅支付多少元钱。
输入格式
本题包含多组测试数据。
第一行一个正整数 $T$ 表示数据组数。
对于每组数据,第一行一个整数 $n$,第二行 $n$ 个由空格分隔的整数,第 $i$ 个数表示 $a_i$。
输出格式
共 $T$ 行,每组数据输出一行一个整数表示答案。
样例
样例 $1$
样例输入
3
4
3 1 2 1
6
2 1 1 3 2 2
8
17 10 13 11 11 8 14 14
样例输出
3
1
11
样例 $2$
见附件中 modify2.in
和 modify2.ans
。
数据范围
本题采用捆绑测试。
对于所有数据,保证 $2\le n\le 10^5,1\le a_i\le 10^9,\sum n\le 2\cdot 10^5$。
- Subtask 1($1$ points):$a_i=1$。
- Subtask 2($2$ points):$T=3,n=2$。
- Subtask 3($15$ points):$a_i\le a_{i+1}$。
- Subtask 4($6$ points):$n\le 6$。
- Subtask 5($6$ points):$T=1,n\le 36$。
- Subtask 6($6$ points):$T\le 36,n\le 36$。
- Subtask 7($6$ points):$T=1,n\le 149$。
- Subtask 8($6$ points):$n\le 149$,存在一个 $1\le k\le n$ 使得任意 $1\le i\le k-1$ 都有 $a_i\ge a_{i+1}$,任意 $i\le k\le n-1$ 都有 $a_i\le a_{i+1}$。
- Subtask 9($18$ points):$T=1,n\le 1379$。
- Subtask 10($6$ points):$T=1$。
- Subtask 11($28$ points):无特殊限制。