CF1591D.Yet Another Sorting Problem

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.

佩佳有一个整数数组 $a_1, a_2, \ldots, a_n$。他只喜欢有序数组。然而，给定的数组可能是任意的，因此佩佳希望将它排序。

佩佳喜欢挑战自我，因此他希望仅使用 3-轮换（3-cycle） 来对数组进行排序。更准确地说，一次操作中，他可以选择三个互不相同的下标 $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]$。

佩佳可以执行任意次数（包括零次）的 3-轮换操作。你需要判断佩佳是否能将数组 $a$ 排序成非递减序列。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

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).

对于每个测试用例，如果 Petya 可以使用 $3$-轮换对数组 $a$ 进行排序，则输出 "YES"（不带引号）；否则输出 "NO"（不带引号）。每个字母可以以任意大小写形式输出（大写或小写）。

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.

在第 $6$ 个测试用例中，Petya 可以使用 $3$-循环 $1 \to 3 \to 2 \to 1$ 对数组进行排序。

在第 $7$ 个测试用例中，Petya 可以先应用 $1 \to 3 \to 2 \to 1$，使 $a = [1, 4, 2, 3]$；然后应用 $2 \to 4 \to 3 \to 2$，最终完成数组的排序。