AT_arc181_a [ARC181A] Sort Left and Right

题目描述

给你一个 $(1,2,\dots,N)$ 的排列 $P=(P_1,P_2,\dots,P_N)$。

你要通过执行以下操作零次或多次来满足所有 $i=1,2,\dots,N$ 的 $P_i=i$：

• 选择一个整数 $k$，使得 $1 \leq k \leq N$。如果是 $k \geq 2$，把第 $1$ 项到第 $(k-1)$ 项的 $P$ 按升序排序。然后，如果是 $k \leq N-1$，把 $P$ 的第 $(k+1)$ 项到第 $N$ 项按升序排序。

可以证明，在这个问题的约束条件下，对于任意 $P$，都可以用有限次的运算满足所有 $i=1,2,\dots,N$ 的 $P_i=i$。请求解所需的最小运算次数。

输入格式

本题的测试点有多组测试数据。

第一行一个整数 $T$，表示测试组数。

对于每组测试数据，第一行包括一个整数 $N$，第二行包括 $N$ 个整数，表示排列 $P$。

输出格式

输出 $T$ 行，第 $i$ 行表示第 $i$ 组测试数据的答案。

样例 1

输入

3
5
2 1 3 5 4
3
1 2 3
7
3 2 1 7 5 6 4

输出

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$ 满足所有 $i=1,2,\dots,5$ 的 $P_i=i$。因此，所需的最少运算次数为 $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)$ 。

对于 $100\%$ 的测试数据，保证 $1 \leq T \leq 10^5$，$3 \leq N \leq 2 \times 10^5$，$P$ 是 $(1,2,\dots,N)$ 的排列。