/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
(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 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 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 以下
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
各ケースは以下の形式で与えられる。
N P_1 P_2 \dots P_N
出力
T 行出力せよ。i 行目には i 番目のテストケースについて答えを出力せよ。
入力例 1
3 5 2 1 3 5 4 3 1 2 3 7 3 2 1 7 5 6 4
出力例 1
1 0 2
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) と変化します。
Score : 300 points
Problem Statement
You are given a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).
You want to satisfy P_i=i for all i=1,2,\dots,N by performing the following operation zero or more times:
- Choose an integer k such that 1 \leq k \leq N. If k \geq 2, sort the 1-st through (k-1)-th terms of P in ascending order. Then, if k \leq N-1, sort the (k+1)-th through N-th terms of P in ascending order.
It can be proved that under the constraints of this problem, it is possible to satisfy P_i=i for all i=1,2,\dots,N with a finite number of operations for any P. Find the minimum number of operations required.
You have T test cases to solve.
Constraints
- 1 \leq T \leq 10^5
- 3 \leq N \leq 2 \times 10^5
- P is a permutation of (1,2,\dots,N).
- All input values are integers.
- The sum of N across the test cases in a single input is at most 2 \times 10^5.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
Each case is given in the following format:
N P_1 P_2 \dots P_N
Output
Print T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
3 5 2 1 3 5 4 3 1 2 3 7 3 2 1 7 5 6 4
Sample Output 1
1 0 2
For the first test case,
-
Performing the operation with k=1 results in P becoming (2,1,3,4,5).
-
Performing the operation with k=2 results in P becoming (2,1,3,4,5).
-
Performing the operation with k=3 results in P becoming (1,2,3,4,5).
-
Performing the operation with k=4 results in P becoming (1,2,3,5,4).
-
Performing the operation with k=5 results in P becoming (1,2,3,5,4).
Specifically, performing the operation with k=3 results in P satisfying P_i=i for all i=1,2,\dots,5. Therefore, the minimum number of operations required is 1.
For the third test case, performing the operation with k=4 followed by k=3 results in P changing as (3,2,1,7,5,6,4) \rightarrow (1,2,3,7,4,5,6) \rightarrow (1,2,3,4,5,6,7).