题目描述

有一个 $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

输入 #1

5
5
5 2 1 3 4
2
1 1
3
1 3 1
9
9 9 8 2 4 4 3 5 3
20
7 4 6 2 15 5 17 15 1 8 18 1 5 1 12 11 2 7 8 14

输出 #1

4
0
1
16
105

说明/提示

样例解释 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 翻译