CF1372C Omkar and Baseball

Patrick 喜欢打棒球，但有时候他会花太多时间击出本垒打，导致头脑变得模糊！Patrick 确信他在 $n$ 场比赛中的得分是一个恒等排列（即第一场得 $1$ 分，第二场得 $2$ 分，依此类推）。然而，当他回头查看自己的记录时，发现所有的数字都被打乱了！ 定义一种特殊交换如下：选择分数序列的任意一个子数组，并对其元素进行排列，使得子数组中的每个元素都不能回到原来的位置。例如，对 $[1,2,3]$ 进行一次特殊交换可以得到 $[3,1,2]$，但不能得到 $[3,2,1]$，因为 $2$ 仍然在原来的位置。 给定一个长度为 $n$ 的排列，请帮助 Patrick 求出将该排列变为有序所需的最少特殊交换次数！可以证明，在给定的约束下，这个次数不会超过 $10^{18}$。 如果数组 $a$ 是数组 $b$ 的一个子数组，那么 $a$ 可以通过从 $b$ 的开头删除若干（可能为零或全部）元素，以及从末尾删除若干（可能为零或全部）元素得到。

每个测试包含多个测试用例。第一行为测试用例数 $t$（$1 \le t \le 100$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示给定排列的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（$1 \leq a_{i} \leq n$），表示初始排列。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示将该排列变为有序所需的最少特殊交换次数。

在第一个排列中，已经是有序的，因此不需要任何交换。 可以证明，第二个排列至少需要 $2$ 次交换才能变为有序。 $[3, 2, 4, 5, 1, 6, 7]$ 对区间 $(1, 5)$ 进行一次特殊交换： $[4, 1, 2, 3, 5, 6, 7]$ 对区间 $(1, 4)$ 再进行一次特殊交换： $[1, 2, 3, 4, 5, 6, 7]$ 由 ChatGPT 4.1 翻译