Yet Another Sorting Problem

题意翻译

### 题意简述 给定一个数组 $a_1,a_2,\dots,a_n$，询问是否能用有限次操作使其单调不减。 这里将一次操作定义为将 $a_i,a_j,a_k$ （$i,j,k$ 互不相等）的值轮换，即将其分别设为 $a_j,a_k,a_i$。 ### 输入格式 第一行一个整数 $t(1 \leq t \leq 5 \times 10^5)$，代表数据组数。 对于每一组数据，第一行一个整数 $n(1 \leq n \leq 5 \times 10^5)$，代表数组 $a$ 的长度，第二行 $n$ 个整数，代表 $a_1,a_2,\dots,a_n(1 \leq a_i \leq n)$。 保证 $\sum n \leq 5 \times 10^5$。 ### 输出格式 输出共 $t$ 行，每行为一个字符串 "YES" 或 "NO"（大小写随意），代表第 $i$ 组数据的答案。 ###### 翻译:@AFOI

题目描述

Petya has an array of integers $ a_1, a_2, \ldots, a_n $ . He only likes sorted arrays. Unfortunately, the given array could be arbitrary, so Petya wants to sort it. Petya likes to challenge himself, so he wants to sort array using only $ 3 $ -cycles. More formally, in one operation he can pick $ 3 $ pairwise distinct indices $ i $ , $ j $ , and $ k $ ( $ 1 \leq i, j, k \leq n $ ) and apply $ i \to j \to k \to i $ cycle to the array $ a $ . It simultaneously places $ a_i $ on position $ j $ , $ a_j $ on position $ k $ , and $ a_k $ on position $ i $ , without changing any other element. For example, if $ a $ is $ [10, 50, 20, 30, 40, 60] $ and he chooses $ i = 2 $ , $ j = 1 $ , $ k = 5 $ , then the array becomes $ [\underline{50}, \underline{40}, 20, 30, \underline{10}, 60] $ . Petya can apply arbitrary number of $ 3 $ -cycles (possibly, zero). You are to determine if Petya can sort his array $ a $ , i. e. make it non-decreasing.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \leq t \leq 5 \cdot 10^5 $ ). Description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 5 \cdot 10^5 $ ) — the length of the array $ a $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5 \cdot 10^5 $ .

输出格式

For each test case, print "YES" (without quotes) if Petya can sort the array $ a $ using $ 3 $ -cycles, and "NO" (without quotes) otherwise. You can print each letter in any case (upper or lower).

输入输出样例

输入样例 #1

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

输出样例 #1

YES
YES
NO
YES
NO
YES
YES

说明

In the $ 6 $ -th test case Petya can use the $ 3 $ -cycle $ 1 \to 3 \to 2 \to 1 $ to sort the array. In the $ 7 $ -th test case Petya can apply $ 1 \to 3 \to 2 \to 1 $ and make $ a = [1, 4, 2, 3] $ . Then he can apply $ 2 \to 4 \to 3 \to 2 $ and finally sort the array.