AT_abc443_d [ABC443D] Pawn Line

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.

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 $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 This input contains five test cases. For the first test case, by performing operations as follows, you can satisfy the condition in the problem statement with four operations, which is the minimum. - Move the piece in the $ 5 $ -th column from the left to the cell directly above it. The pieces are in rows $ 5,2,1,3,3 $ from left to right. - Move the piece in the $ 1 $ -st column from the left to the cell directly above it. The pieces are in rows $ 4,2,1,3,3 $ from left to right. - Move the piece in the $ 1 $ -st column from the left to the cell directly above it. The pieces are in rows $ 3,2,1,3,3 $ from left to right. - Move the piece in the $ 4 $ -th column from the left to the cell directly above it. The pieces are in rows $ 3,2,1,2,3 $ from left to right. For the second test case, the condition is satisfied without performing any operations. ### 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 $ .