A. Сувлаки против Каламаки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Двум игрокам, Сувлаки и Каламаки, дана последовательность $$$a$$$ из $$$n$$$ целых чисел.

Они будут играть в игру, состоящую из $$$n-1$$$ раундов, пронумерованных от $$$1$$$ до $$$n-1$$$. Сувлаки играет в раундах с нечётными номерами, а Каламаки — в раундах с чётными номерами.

В $$$i$$$-м раунде игрок должен выполнить одно из следующих двух действий:

  • Пропустить свой ход и перейти к раунду $$$i+1$$$ (или закончить игру, если раунд $$$i$$$ был последним).
  • Поменять местами элементы $$$a_i$$$ и $$$a_{i+1}$$$.

Сувлаки выигрывает, если после окончания последнего раунда $$$a$$$ отсортировано в неубывающем порядке. Другими словами, он выигрывает, если выполняется условие $$$a_i \le a_{i+1}$$$ для каждого $$$1 \le i \lt n$$$. В противном случае выигрывает Каламаки.

Однако Сувлаки не любит проигрывать, поэтому до начала игры он может переупорядочить элементы $$$a$$$ любым способом, который он хочет. Возможно ли сделать это так, чтобы у него была гарантированная выигрышная стратегия?

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 100$$$) — количество целых чисел в $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$), где $$$a_i$$$ обозначает $$$i$$$-й элемент $$$a$$$.

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

Для каждого набора входных данных выведите на отдельной строке «YES», если Сувлаки может переупорядочить элементы $$$a$$$ так, чтобы у него была гарантированная выигрышная стратегия, и «NO» в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
5
4
4 2 2 1
4
1 1 1 1
5
1 5 1 5 1
3
1 2 3
5
1 3 2 3 5
Выходные данные
YES
YES
YES
NO
NO
Примечание

В первом наборе входных данных, $$$a = [4, 2, 2, 1]$$$. Возможный способ переупорядочить элементы так, чтобы Сувлаки мог выиграть, следующий: $$$a = [2, 1, 2, 4]$$$. Тогда игра может проходить следующим образом:

  1. В раунде $$$1$$$ ходит Сувлаки. Он выберет поменять местами $$$a_1$$$ с $$$a_2$$$, и теперь $$$a = [1, 2, 2, 4]$$$.
  2. В раунде $$$2$$$ ходит Каламаки. Независимо от того, выберет он пропустить свой ход или поменять местами элементы $$$a_2$$$ и $$$a_3$$$, $$$a$$$ останется прежним. Предположим, что он пропускает свой ход.
  3. В раунде $$$3$$$ ходит Сувлаки. Он также может выбрать пропустить свой ход, потому что если он поменяет местами последние два элемента, он проиграет.

После каждого раунда $$$a = [1, 2, 2, 4]$$$, отсортировано в неубывающем порядке, так что Сувлаки выигрывает независимо от того, как решит играть Каламаки.

Во втором наборе входных данных, поскольку все элементы равны, Сувлаки всегда выиграет, потому что $$$a$$$ всегда отсортировано в неубывающем порядке.