Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:1024 MB
Statistics

修线(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.inmodify2.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):无特殊限制。

下发文件