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

У вас есть $$$n$$$ карточек, расположенных в ряд. На $$$i$$$-й карточке написано целое число $$$a_i$$$. Все числа различны.

Вы должны раскрасить каждую карточку либо в $$$\color{red}{\text{красный}}$$$, либо в $$$\color{blue}{\text{синий}}$$$ так, чтобы были выполнены следующие условия:

  • Любые две соседние карточки в ряду имеют разные цвета.
  • Если вы переставите карточки так, чтобы числа на них были в порядке возрастания, любые две соседние карточки в новом ряду также должны иметь разные цвета.

Определите, существует ли такая раскраска.

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

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

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

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

Гарантируется, что все элементы $$$a$$$ различны.

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

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

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

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

В первом наборе входных данных карточки раскрашены как $$$a = [\color{red}{2}, \color{blue}{3}, \color{red}{4}, \color{blue}{1}]$$$. После сортировки карточки становятся $$$[\color{blue}{1}, \color{red}{2}, \color{blue}{3}, \color{red}{4}]$$$. Обе последовательности удовлетворяют условию, поэтому ответ YES.

Во втором наборе входных данных не существует допустимой раскраски. Например, если мы раскрасим карточки как $$$a = [\color{blue}{2}, \color{red}{3}, \color{blue}{1}]$$$, отсортированная последовательность станет $$$[\color{blue}{1}, \color{blue}{2}, \color{red}{3}]$$$. Здесь соседние элементы $$$1$$$ и $$$2$$$ имеют один и тот же цвет, поэтому условие не выполнено.

В третьем наборе входных данных возможная раскраска: $$$a = [\color{blue}{3}, \color{red}{4}, \color{blue}{1}, \color{red}{2}, \color{blue}{5}]$$$. После сортировки карточки становятся $$$[\color{blue}{1}, \color{red}{2}, \color{blue}{3}, \color{red}{4}, \color{blue}{5}]$$$.