CF1585D Yet Another Sorting Problem

Petya 有一个整数数组 $ a_1, a_2, \ldots, a_n $。他只喜欢有序数组。但给定的数组可能是任意的，因此 Petya 想要将其排序。 Petya 喜欢挑战自己，所以他只想使用每次选择三个数进行轮换的方法进行排序。形式化地说，每次操作中，他可以选择三个互不相同的下标 $ i $, $ j $, $ k $（ $ 1 \leq i, j, k \leq n $ ）并对数组 $ a $ 应用 $ i \to j \to k \to i $ 轮换。该操作会同时将 $ a_i $ 放到位置 $ j $，$ a_j $ 放到位置 $ k $，$ a_k $ 放到位置 $ i $，其他元素保持不变。 例如，若 $ a $ 为 $ [10, 50, 20, 30, 40, 60] $ 并选择 $ i = 2 $, $ j = 1 $, $ k = 5 $，则数组变为 $ [\underline{50}, \underline{40}, 20, 30, \underline{10}, 60] $。 Petya 可以进行任意次（包括零次）的轮换操作。你需要判断 Petya 是否能将数组 $ a $ 排序为一个单调不减的序列。

每个测试包含多个测试用例。第一行包含测试用例数量 $ t $（ $ 1 \leq t \leq 5 \cdot 10^5 $ ）。接下来是测试用例描述。 每个测试用例的第一行包含一个整数 $ n $（ $ 1 \leq n \leq 5 \cdot 10^5 $ ）——数组 $ a $ 的长度。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（ $ 1 \leq a_i \leq n $ ）。 保证所有测试用例的 $ n $ 之和不超过 $ 5 \cdot 10^5 $。

对于每个测试用例，如果 Petya 能用 $ 3 $ -轮换操作排序数组 $ a $，输出 "YES"（不带引号），否则输出 "NO"（不带引号）。输出字母大小写任意。

在第六个测试用例中，Petya 可以使用 $ 3 $ -轮换 $ 1 \to 3 \to 2 \to 1 $ 来排序数组。 在第七个测试用例中，Petya 可以先应用 $ 1 \to 3 \to 2 \to 1 $ 得到 $ a = [1, 4, 2, 3] $，再应用 $ 2 \to 4 \to 3 \to 2 $ 完成排序。 ---- 翻译由 DeepSeek 生成。