D - Pawn Line Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N \times N のマス目があり、各列に 1 つずつ駒が置かれています。
i 列目の駒は上から R_i 行目に置かれています。

あなたは以下の操作を 0 回以上何度でも行うことができます。

  • 一番上の行以外に存在する駒をひとつ選び、その駒を 上に隣接するマス に移動させる。

以下の条件を 1 \le i \le N-1 を満たす全ての整数 i について満たすようにするために必要な操作回数の最小値を求めて下さい。

  • i 列目の駒が上から x 行目、 i+1 列目の駒が上から y 行目に存在するとする。このとき、 |x-y| \le 1 を満たす。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 入力は全て整数
  • 1 \le T \le 50000
  • 2 \le N \le 3 \times 10^5
  • 1 \le R_i \le N
  • ひとつの入力について、 N の総和は 3 \times 10^5 を超えない

入力

入力は以下の形式で標準入力から与えられる。

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

各テストケースは以下の形式で与えられる。

N
R_1 R_2 \dots R_N

出力

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

この入力には 5 個のテストケースが含まれます。

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 行目に存在する。

2 番目のテストケースについて、操作を行わなくても問題文中の条件を満たしています。

Score : 400 points

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.

Sample Input 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

Sample Output 1

4
0
1
16
105

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.