AT_arc181_a [ARC181A] Sort Left and Right

[problemUrl]: https://atcoder.jp/contests/arc181/tasks/arc181_a $ (1,2,\dots,N) $ の順列 $ P=(P_1,P_2,\dots,P_N) $ が与えられます。 以下の操作を $ 0 $ 回以上行うことで、 $ i=1,2,\dots,N $ に対し $ P_i=i $ が成り立つようにしたいです。 - $ 1\ \leq\ k\ \leq\ N $ を満たす整数 $ k $ を選ぶ。 まず $ 2\ \leq\ k $ ならば $ P $ の $ 1 $ 項目から $ k-1 $ 項目を昇順に並び替える。その後、$ k\ \leq\ N-1 $ ならば $ P $ の $ k+1 $ 項目から $ N $ 項目を昇順に並び替える。 この問題の制約の下ではどのような $ P $ に対しても有限回の操作で $ i=1,2,\dots,N $ に対し $ P_i=i $ が成り立つようにできることが証明できます。必要な最小の操作回数を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ 各ケースは以下の形式で与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $

$ T $ 行出力せよ。$ i $ 行目には $ i $ 番目のテストケースについて答えを出力せよ。

### 制約 - $ 1\ \leq\ T\ \leq\ 10^5 $ - $ 3\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ P $ は $ (1,2,\dots,N) $ の順列 - 入力される値はすべて整数 - $ 1 $ つの入力に含まれるテストケースについて、 $ N $ の総和は $ 2\ \times\ 10^5 $ 以下 ### Sample Explanation 1 $ 1 $ 番目のテストケースについて、 - $ k=1 $ として操作を行うと、 $ P $ は $ (2,1,3,4,5) $ になります。 - $ k=2 $ として操作を行うと、 $ P $ は $ (2,1,3,4,5) $ になります。 - $ k=3 $ として操作を行うと、 $ P $ は $ (1,2,3,4,5) $ になります。 - $ k=4 $ として操作を行うと、 $ P $ は $ (1,2,3,5,4) $ になります。 - $ k=5 $ として操作を行うと、 $ P $ は $ (1,2,3,5,4) $ になります。 特に $ k=3 $ として操作を行った場合、操作後 $ i=1,2,\dots,5 $ に対し $ P_i=i $ が成り立ちます。よって必要な最小の操作回数は $ 1 $ です。 $ 3 $ 番目のテストケースについて、 $ k=4 $ として操作を行った後、 $ k=3 $ として操作を行うと $ P $ は $ (3,2,1,7,5,6,4)\rightarrow\ (1,2,3,7,4,5,6)\ \rightarrow\ (1,2,3,4,5,6,7) $ と変化します。