CF1372C.Omkar and Baseball

Patrick likes to play baseball, but sometimes he will spend so many hours hitting home runs that his mind starts to get foggy! Patrick is sure that his scores across $n$ sessions follow the identity permutation (ie. in the first game he scores $1$ point, in the second game he scores $2$ points and so on). However, when he checks back to his record, he sees that all the numbers are mixed up!

Define a special exchange as the following: choose any subarray of the scores and permute elements such that no element of subarray gets to the same position as it was before the exchange. For example, performing a special exchange on $[1,2,3]$ can yield $[3,1,2]$ but it cannot yield $[3,2,1]$ since the $2$ is in the same position.

Given a permutation of $n$ integers, please help Patrick find the minimum number of special exchanges needed to make the permutation sorted! It can be proved that under given constraints this number doesn't exceed $10^{18}$.

An array $a$ is a subarray of an array $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

帕特里克喜欢打棒球，但有时他会花上数小时击出本垒打，以至于头脑开始变得模糊！帕特里克确信自己在 $n$ 场比赛中的得分遵循恒等排列（即：第一场得分为 $1$ 分，第二场得分为 $2$ 分，依此类推）。然而，当他回看自己的记录时，却发现所有数字都乱序了！

定义一次特殊交换如下：任选一个得分子数组，并对该子数组内的元素进行重排，使得子数组中没有任何一个元素保留在其原来的位置上。例如，对 $[1,2,3]$ 执行一次特殊交换可得到 $[3,1,2]$，但不能得到 $[3,2,1]$，因为其中的 $2$ 仍处于原位置。

给定一个由 $n$ 个整数组成的排列，请帮助帕特里克求出使其变为升序排列所需的最少特殊交换次数！在本题约束下可以证明，该最小次数不会超过 $10^{18}$。

若数组 $a$ 可通过从数组 $b$ 的开头删除若干（可能为零或全部）元素、再从结尾删除若干（可能为零或全部）元素而得到，则称 $a$ 是 $b$ 的一个子数组。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the given permutation.

The second line of each test case contains $n$ integers $a_{1},a_{2},...,a_{n}$ ($1 \leq a_{i} \leq n$) — the initial permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output one integer: the minimum number of special exchanges needed to sort the permutation.

对于每个测试用例，输出一个整数：对排列进行排序所需的最少特殊交换次数。

In the first permutation, it is already sorted so no exchanges are needed.

It can be shown that you need at least $2$ exchanges to sort the second permutation.

$[3, 2, 4, 5, 1, 6, 7]$

Perform special exchange on range ($1, 5$)

$[4, 1, 2, 3, 5, 6, 7]$

Perform special exchange on range ($1, 4$)

$[1, 2, 3, 4, 5, 6, 7]$

在第一个排列中，它已经是有序的，因此不需要任何交换。

可以证明，要将第二个排列排序，至少需要 $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]$