Problem Statement

There is an $N \times N$ grid, and there is one piece placed in each column. The piece in column $i$ is placed in row $R_i$ from the top.

You can perform the following operation zero or more times:

• Choose a piece that is not in the topmost row and move that piece to the cell directly above it.

Find the minimum number of operations needed to satisfy the following condition for all integers $i$ satisfying $1 \le i \le N-1$:

• Let the piece in column $i$ be in row $x$ from the top and the piece in column $i+1$ be in row $y$ from the top. Then, $|x-y| \le 1$.

You are given $T$ test cases; solve each of them.

Constraints

• All input values are integers.
• $1 \le T \le 50000$
• $2 \le N \le 3 \times 10^5$
• $1 \le R_i \le N$
• For a single input, the sum of $N$ does not exceed $3 \times 10^5$.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N
R_1 R_2 \dots R_N

Output

Output $T$ lines.

The $i$-th line should contain the answer for the $i$-th test case.