修线（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）：无特殊限制。