有一个 N \times N 的网格，每一列各放一个棋子。第 i 列的棋子放在从上往下数第 R_i 行。

你可以进行以下操作任意次（含 0 次）：

- 选择一个不在最上面一行的棋子，将其移动到正上方的相邻格子。

请计算：为了对所有满足 1 \le i \le N-1 的整数 i 满足以下条件，所需的最少操作次数：

- 设第 i 列的棋子在第 x 行、第 i+1 列的棋子在第 y 行，则 |x-y| \le 1。

给定 T 个测试用例，请分别求出每个用例的答案。

输入以如下格式从标准输入给出：

T

case_1

case_2

...

case_T

每个测试用例以如下格式给出：

N

R_1 R_2 ... R_N

输出 T 行。

第 i 行输出第 i 个测试用例的答案。

样例1说明：

第 1 个用例中，例如将第 1 列的棋子从第 5 行移动到第 3 行（2 次）、第 2 列的棋子从第 2 行移动到第 2 行（0 次）……最终各列高度为 3,2,1,2,3，相邻列高度差均不超过 1，共 4 次。

- 输入均为整数。

- 1 \le T \le 50000

- 2 \le N \le 3 \times 10^5

- 1 \le R_i \le N

- 单个输入中 N 的总和不超过 3 \times 10^5。