AT_abc443_d [ABC443D] Pawn Line

$ 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 $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ R_1 $ $ R_2 $ $ \dots $ $ R_N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 この入力には $ 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 $ 番目のテストケースについて、操作を行わなくても問題文中の条件を満たしています。 ### Constraints - 入力は全て整数 - $ 1 \le T \le 50000 $ - $ 2 \le N \le 3 \times 10^5 $ - $ 1 \le R_i \le N $ - ひとつの入力について、 $ N $ の総和は $ 3 \times 10^5 $ を超えない