← 返回题目列表

AtCoder · arc181_a

A. 左右排序

中文机器翻译题面 查看原题

分数: 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).