题目描述

给定一个 $N\times N$ 的网格棋盘，每一列上放有一个棋子。第 $i$ 列的棋子位于从上往下数的第 $R_i$ 行（$1\le R_i\le N$）。你可以重复任意次以下操作：

• 选择一个 不在最顶部行 的棋子，将该棋子向上移动一格（行号减 $1$）。

要求用最少的操作次数，使得对于所有 $1\le i\le N-1$，记第 $i$ 列棋子所在行为从上往下数的第 $x$ 行、第 $i+1$ 列棋子所在行为从上往下数的第 $y$ 行，满足 $|x-y|\le 1$ 。

给出 $T$ 个测试用例，请你对每个测试用例输出最小操作次数。

输入格式

输入包含多组测试数据。

• 第一行包含一个整数 $T$ （$1 \le T\le 5 \times 10^4$），表示测试用例数。

• 随后对每个测试用例：

  • 第一行包含一个整数 $N$（$2\le N\le 3\times 10^5$），
  • 第二行包含 $N$ 个整数 $R_1,R_2,\dots,R_N$，其中 $1\le R_i\le N$。

对于一个输入文件，所有测试用例的 $N$ 之和不会超过 $3\times 10^5$。

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的最小操作次数（一个整数）。

样例输入 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

说明

样例解释

样例包含五个测试用例。

• 第一个测试用例（一种可行的最少 $4$ 步方案）：

  1. 将第 $5$ 列的棋子上移一格，行数变为 $5,2,1,3,3$；
  2. 将第 $1$ 列的棋子上移一格，行数变为 $4,2,1,3,3$；
  3. 将第 $1$ 列的棋子再上移一格，行数变为 $3,2,1,3,3$；
  4. 将第 $4$ 列的棋子上移一格，行数变为 $3,2,1,2,3$。

  此时相邻两列行差均不超过 $1$，且不能用更少步数完成。

• 第二个测试用例已满足条件，无需任何操作，答案为 $0$。