AT_abc443_d [ABC443D] Pawn Line

有一个 $N \times N$ 的网格，每一列上都放有一个棋子。 第 $i$ 列的棋子放在从顶部数起第 $R_i$ 行。 你可以进行如下操作若干次（可以为零次）： - 选择一个不在最顶行的棋子，将该棋子移动到其正上方的格子。 请你求出，为了满足以下条件，对所有满足 $1 \le i \le N-1$ 的整数 $i$，最少需要操作多少次： - 设第 $i$ 列的棋子在从上往下第 $x$ 行，第 $i+1$ 列的棋子在从上往下第 $y$ 行，则 $|x-y| \le 1$。 给定 $T$ 组测试数据，请分别求解。

输入从标准输入读入，格式如下： > $T$ > 第 1 组数据： $N\quad R_1\quad R_2\quad \dots\quad R_N$ > 第 2 组数据： $N\quad R_1\quad R_2\quad \dots\quad R_N$ > $\vdots$ > 第 $T$ 组数据： $N\quad R_1\quad R_2\quad \dots\quad R_N$

输出 $T$ 行。 第 $i$ 行输出第 $i$ 组测试数据的答案。

## 样例解释 1 该输入含有五组测试数据。 对于第一组数据，可以依次进行如下操作，使得题目条件成立且操作次数最少，为 4 次： - 将第 5 列的棋子上移一格，此时各列棋子所在行为 $5,2,1,3,3$。 - 将第 1 列的棋子上移一格，此时各列棋子所在行为 $4,2,1,3,3$。 - 将第 1 列的棋子再上移一格，此时各列棋子所在行为 $3,2,1,3,3$。 - 将第 4 列的棋子上移一格，此时各列棋子所在行为 $3,2,1,2,3$。 对于第二组数据，已经满足条件，无需操作。 ## 约束条件 - 所有输入值均为整数。 - $1 \le T \le 50000$ - $2 \le N \le 3 \times 10^5$ - $1 \le R_i \le N$ - 所有测试数据中 $N$ 的总和不超过 $3 \times 10^5$。 由 ChatGPT 5 翻译