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.

输入输出样例

输入样例 #1

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

输出样例 #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.

**题目大意：**

题目给出了一个整数 $ n $ 和一个从 $ 1 $ 到 $ n $ 的排列 $ p $。你可以进行任意次以下操作：

- 选择整数 $ i, j (1 \leq i < j \leq n) $，然后交换 $ p_i, p_j $ 的值。

要求出至少需要进行多少次上述操作才能使得排列 $ p $ 恰好有一个逆序对。每个测试点包含 $ t $ 组数据。

**输入输出数据格式：**

**输入格式：**

第一行输入一个整数 $ t (1 \leq t \leq 10^4) $ 表示数据组数。接下来对于每组数据：

- 第一行输入一个整数 $ n (2 \leq n, \sum n \leq 2 \times 10^5) $。
- 接下来输入一行 $ n $ 个整数 $ p_1, p_2, \cdots, p_n (1 \leq p_i \leq n) $，保证 $ p $ 是一个从 $ 1 $ 到 $ n $ 的排列。

**输出格式：**

对于每组数据：

- 输出一行一个整数，表示使排列 $ p $ 恰有一个逆序对所需的最小操作次数。

可以证明一定存在操作方案使得 $ p $ 恰有一个逆序对。

---

**题目描述（英文）：**

You are given a permutation $ p $ of length $ n $.

In one operation, you can choose two indices $ 1 \leq i < j \leq n $ and swap $ p_i $ with $ p_j $.

Find the minimum number of operations needed to have exactly one inversion in the permutation.

**输入输出格式：**

**输入格式：**

The first line contains a single integer $ t (1 \leq t \leq 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 \leq n \leq 2 \times 10^5) $.

The second line of each test case contains $ n $ integers $ p_1, p_2, \ldots, p_n (1 \leq p_i \leq 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 \times 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.**题目大意：** 题目给出了一个整数 $ n $ 和一个从 $ 1 $ 到 $ n $ 的排列 $ p $。你可以进行任意次以下操作： - 选择整数 $ i, j (1 \leq i < j \leq n) $，然后交换 $ p_i, p_j $ 的值。 要求出至少需要进行多少次上述操作才能使得排列 $ p $ 恰好有一个逆序对。每个测试点包含 $ t $ 组数据。 **输入输出数据格式：** **输入格式：** 第一行输入一个整数 $ t (1 \leq t \leq 10^4) $ 表示数据组数。接下来对于每组数据： - 第一行输入一个整数 $ n (2 \leq n, \sum n \leq 2 \times 10^5) $。 - 接下来输入一行 $ n $ 个整数 $ p_1, p_2, \cdots, p_n (1 \leq p_i \leq n) $，保证 $ p $ 是一个从 $ 1 $ 到 $ n $ 的排列。 **输出格式：** 对于每组数据： - 输出一行一个整数，表示使排列 $ p $ 恰有一个逆序对所需的最小操作次数。 可以证明一定存在操作方案使得 $ p $ 恰有一个逆序对。 --- **题目描述（英文）：** You are given a permutation $ p $ of length $ n $. In one operation, you can choose two indices $ 1 \leq i < j \leq n $ and swap $ p_i $ with $ p_j $. Find the minimum number of operations needed to have exactly one inversion in the permutation. **输入输出格式：** **输入格式：** The first line contains a single integer $ t (1 \leq t \leq 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 \leq n \leq 2 \times 10^5) $. The second line of each test case contains $ n $ integers $ p_1, p_2, \ldots, p_n (1 \leq p_i \leq 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 \times 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.