CF1863B Split Sort

给定一个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$，排列是 $1$ 到 $n$ 的整数的一个任意顺序排列。 你可以对当前排列进行若干次（也可以为零次）如下操作： - 选择某个 $x$（$2 \le x \le n$）； - 创建一个新排列，方法如下： - 首先，按原顺序写下所有小于 $x$ 的元素； - 然后，按原顺序写下所有大于等于 $x$ 的元素； - 用新排列替换当前排列。 例如，若当前排列为 $[6, 4, 3, 5, 2, 1]$，选择 $x = 4$，则先写下 $[3, 2, 1]$，再接上 $[6, 4, 5]$，得到新排列 $[3, 2, 1, 6, 4, 5]$。 请你求出，最少需要多少次操作才能使排列变为 $p_i = i$，即 $[1, 2, \ldots, n]$。可以证明一定可以做到。 $^\dagger$ 长度为 $n$ 的排列是 $1$ 到 $n$ 的 $n$ 个互不相同的整数的任意顺序。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$ 但出现了 $4$）。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 100\,000$）。 第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$）。保证 $p_1, p_2, \ldots, p_n$ 是一个排列。 保证所有测试用例中 $n$ 的总和不超过 $100\,000$。

对于每组测试用例，输出一个整数，表示最少需要的操作次数。每个答案占一行。

在第一个测试用例中，$n=1$ 且 $p_1=1$，无需操作。 在第二个测试用例中，可以选择 $x=2$，立即得到 $p_1=1, p_2=2$。 在第三个测试用例中，可以按如下方式达到最少操作次数： 1. $x=4$：$[6, 4, 3, 5, 2, 1] \rightarrow [3, 2, 1, 6, 4, 5]$； 2. $x=6$：$[3, 2, 1, 6, 4, 5] \rightarrow [3, 2, 1, 4, 5, 6]$； 3. $x=3$：$[3, 2, 1, 4, 5, 6] \rightarrow [2, 1, 3, 4, 5, 6]$； 4. $x=2$：$[2, 1, 3, 4, 5, 6] \rightarrow [1, 2, 3, 4, 5, 6]$。 由 ChatGPT 4.1 翻译