Omkar and Baseball
Contest: Codeforces Round 655 (Div. 2)
Difficulty rating: 1500
Tags: constructive algorithms, math

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.

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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]$$$

Example input:
2
5
1 2 3 4 5
7
3 2 4 5 1 6 7

Example output:
0
2

Editorial:
You need at most $$$2$$$ special exchanges to sort the permutation. Obviously, $$$0$$$ special exchanges are needed if the array is already sorted. Let's look into cases in which you need $$$1$$$ special exchange to sort the array.
Refer to i as a matching index if $$$a_i = i$$$. If there are no matching indices, then you can just use one special exchange to sort the entire thing. Otherwise, you can use the location of matching indices to determine whether you need more than $$$1$$$ special exchange. If all matching indices are located in some prefix of the permutation, you can sort the permutation with one special exchange. The same is true for a suffix. In other words, if you can choose a subarray in the permutation such that all elements contained in the subarray are NOT matching and the elements outside of this subarray are matching, then one special exchange is needed to sort the array.
Otherwise, you need $$$2$$$ special exchanges to sort the permutation. Let's prove why you do not need more than $$$2$$$ special exchanges. You can quickly check that you need at most $$$2$$$ special exchanges for all permutations of length $$$\leq 3$$$. For permutations of length $$$\geq 4$$$, I claim that we can perform $$$2$$$ special exchanges on the whole array; to show this it suffices to construct a permutation $$$p$$$ that has no matching indices with either the given permutation or the identity permutation $$$1, 2, \ldots, n$$$. We can do this as follows:
For simplicity, assume that $$$n$$$ is even. We will assign the numbers $$$\frac n 2 + 1, \frac n 2 + 2, \ldots, n$$$ to the first $$$\frac n 2$$$ positions of our permutation $$$p$$$ and the numbers $$$1, 2, \ldots, \frac n 2$$$ to the last $$$\frac n 2$$$ positions of $$$p$$$. This ensures that $$$p$$$ has no matching indices with the identity permutation. Then, for all integers $$$b$$$ such that their position $$$i$$$ in $$$a$$$ (i. e. the $$$j$$$ such that $$$a_j = b$$$) is in the appropriate half of $$$p$$$, assign $$$p_i = b$$$; assign other $$$b$$$ to arbitrary positions in the appropriate half of $$$p$$$. Finally, cyclically rotate each half of $$$p$$$ – this ensures that $$$p$$$ has no matching indices with $$$a$$$.
As an example, let's take $$$a = [3, 6, 2, 4, 5, 1]$$$. You can quickly check that this cannot be done in less than $$$2$$$ special exchanges. The construction of $$$p$$$ goes as follows:
First, we move all numbers to the proper half of $$$p$$$, so that $$$p = [4, 5, 6, 1, 2, 3]$$$.
Observing that $$$a_2 = 6$$$ and $$$a_6 = 1$$$, we set $$$p_2 = 6$$$ and $$$p_6 = 1$$$ then replace the remaining elements arbitrarily into the correct half, so we can get, for example, $$$p = [4, 6, 5, 2, 3, 1]$$$.
Finally, we cyclically rotate each half of $$$p$$$, obtaining $$$p = [5, 4, 6, 1, 2, 3]$$$, which has no matching indexes with either $$$a = [3, 6, 2, 4, 5, 1]$$$ or $$$[1, 2, 3, 4, 5, 6]$$$.
This can be extended to odd $$$n$$$ by first choosing some element other than $$$1$$$ and $$$a_1$$$ to be $$$p_1$$$ (this works for $$$n \geq 3$$$ and we must have $$$n \geq 5$$$ anyway in this case), and then running the same algorithm on the rest of $$$p$$$.