← 返回题目列表

Codeforces · 1585/D

D. 又一个排序问题

中文机器翻译题面 查看原题

Petya 有一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。他只喜欢排序数组。不幸的是,给定的数组可能是任意的,因此 Petya 想要对其进行排序。

Petya 喜欢挑战自己,因此他想仅使用 $$$3$$$ 周期对数组进行排序。更正式地说,在一次操作中,他可以选择 $$$3$$$ 成对不同索引 $$$i$$$、$$$j$$$ 和 $$$k$$$ ($$$1 \leq i, j, k \leq n$$$) 并将 $$$i \to j \to k \to i$$$ 循环应用于数组 $$$a$$$。它同时将 $$$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, \下划线{10}, 60]$$$。

Petya 可以应用任意数量的 $$$3$$$ 周期(可能为零)。你要确定 Petya 是否可以对他的数组 $$$a$$$ 进行排序,i。 e.使其不减。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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”(不带引号)。您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #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

注意

在第 $$$6$$$ 个测试用例中,Petya 可以使用 $$$3$$$-cycle $$$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$$$ 并最终对数组进行排序。