Lucky Permutation

### 题目描述 给定整数 $n$ 和一个 $1\sim n$ 的排列 $p$。 你可以对排列 $p$ 进行下列操作任意次： - 选择整数 $i,j(1\leq i<j\leq n)$，然后交换 $p_i,p_j$ 的值。 你需要求出至少需要进行上述操作多少次才能使 $p$ 恰有一个逆序对。 每个测试点包含 $t$ 组数据。 ### 输入格式 第一行输入一个整数 $t(1\leq t\leq10^4)$ 表示数据组数，接下来对于每组数据： 第一行输入一个整数 $n(2\leq n,\sum n\leq2\times10^5)$。 接下来输入一行 $n$ 个整数 $p_1,p_2,\cdots,p_n(1\leq p_i\leq n)$，保证 $p$ 是一个 $1\sim n$ 的排列。 ### 输出格式 对于每组数据： 输出一行一个整数表示使 $p$ 恰有一个逆序对所需的最小操作次数。 可以证明一定存在操作方案使得 $p$ 恰有一个逆序对。

You are given a permutation $ ^\dagger $ $ p $ of length $ n $ . In one operation, you can choose two indices $ 1 \le i < j \le n $ and swap $ p_i $ with $ p_j $ . Find the minimum number of operations needed to have exactly one inversion $ ^\ddagger $ in the permutation. $ ^\dagger $ A permutation is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array). $ ^\ddagger $ The number of inversions of a permutation $ p $ is the number of pairs of indices $ (i, j) $ such that $ 1 \le i < j \le n $ and $ p_i > p_j $ .

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ). The second line of each test case contains $ n $ integers $ p_1,p_2,\ldots, p_n $ ( $ 1 \le p_i \le n $ ). It is guaranteed that $ p $ is a permutation. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case output a single integer — the minimum number of operations needed to have exactly one inversion in the permutation. It can be proven that an answer always exists.

4
2
2 1
2
1 2
4
3 4 1 2
4
2 4 3 1

0
1
3
1

In the first test case, the permutation already satisfies the condition. In the second test case, you can perform the operation with $ (i,j)=(1,2) $ , after that the permutation will be $ [2,1] $ which has exactly one inversion. In the third test case, it is not possible to satisfy the condition with less than $ 3 $ operations. However, if we perform $ 3 $ operations with $ (i,j) $ being $ (1,3) $ , $ (2,4) $ , and $ (3,4) $ in that order, the final permutation will be $ [1, 2, 4, 3] $ which has exactly one inversion. In the fourth test case, you can perform the operation with $ (i,j)=(2,4) $ , after that the permutation will be $ [2,1,3,4] $ which has exactly one inversion.