题目描述

给定一个长度为 $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 翻译

样例

5
1
1
2
2 1
6
6 4 3 5 2 1
3
3 1 2
19
10 19 7 1 17 11 8 5 12 9 4 18 14 2 6 15 3 16 13

0
1
4
1
7