D. Ещё одна задача на сортировку
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Пети есть массив целых чисел $$$a_1, a_2, \ldots, a_n$$$. Ему нравятся только отсортированные массивы. К сожалению, имеющийся массив может быть произвольным, поэтому Петя хочет его отсортировать.

Петя любит придумывать различные усложнения, поэтому он хочет осортировать массив, используя только $$$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, \underline{10}, 60]$$$.

Петя может применять произвольное количество $$$3$$$-циклов (возможно, ноль). Определите, может ли Петя отсортировать массив $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите «YES» (без кавычек), если Петя может отсортировать массив $$$a$$$ с помощью $$$3$$$-циклов, и «NO» (без кавычек) в противном случае. Вы можете выводить каждую букву в любом регистре (верхнем или нижнем).

Пример
Входные данные
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
Выходные данные
YES
YES
NO
YES
NO
YES
YES
Примечание

В $$$6$$$-м наборе входных данных Петя может применить $$$3$$$-цикл $$$1 \to 3 \to 2 \to 1$$$ для сортировки массива.

В $$$7$$$-м наборе входных данных Петя может сначала применить $$$1 \to 3 \to 2 \to 1$$$, получив $$$a = [1, 4, 2, 3]$$$. Затем он может применить $$$2 \to 4 \to 3 \to 2$$$ и окончательно отсортировать массив.