分数: 300 点
问题陈述
给你一个排列 P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).
你想要满足 P_i=i 对于所有人 i=1,2,\dots,N 通过执行以下操作零次或多次:
- 选择一个整数 k 这样 1 \leq k \leq N。如果 k \geq 2,排序 1-st 通过 (k-1)第项 P 按升序排列。那么,如果 k \leq N-1,排序 (k+1)-th 通过 N第项 P 按升序排列。
可以证明,在本问题的约束下,可以满足 P_i=i 对于所有人 i=1,2,\dots,N 对于任何有限数量的操作 P。求出所需的最少操作次数。
你有 T 测试用例解决。
约束
- 1 \leq T \leq 10^5
- 3 \leq N \leq 2 \times 10^5
- P 是一个排列 (1,2,\dots,N).
- 所有输入值均为整数。
- 总和 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
对于第一个测试用例,
-
执行操作 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 结果 P 满意 P_i=i 对于所有人 i=1,2,\dots,5。因此,所需的最少操作次数为 1.
对于第三个测试用例,执行操作 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).