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

У AquaMoon есть $$$n$$$ друзей. Они встали в ряд. $$$i$$$-й слева друг надел футболку с числом $$$a_i$$$, написанным на ней. Каждый друг смотрит в одну из двух сторон налево или направо. В начале все друзья смотрят направо.

AquaMoon может делать операции с друзьями. На каждой операции AquaMoon может выбрать два соседних в ряду друга и поменять их местами. После каждой операции оба друга изменяют направление, в котором смотрели, на противоположное: если кто-то смотрел налево, он будет смотреть направо, и наоборот.

AquaMoon надеется, что после нескольких операций числа, написанные на футболках у $$$n$$$ друзей станут неубывающими, если смотреть на них слева направо. Также она хочет, чтобы в этот момент все друзья смотрели направо. Установите, возможно ли это.

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

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

В первой строке описания каждого набора входных данных находится единственное целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество друзей Aquamoon.

Во второй строке находится $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — числа, записанные на футболках.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

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

Вы можете выводить каждую букву в любом регистре (строчную или заглавную).

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

Возможная последовательность операций для первого набора входных данных:

  1. Поменять $$$a_1$$$ и $$$a_2$$$. В результате последовательность чисел $$$3, 4, 2, 5$$$. Друзья смотрят: налево, налево, направо, направо.
  2. Поменять $$$a_2$$$ и $$$a_3$$$. В результате последовательность чисел $$$3, 2, 4, 5$$$. Друзья смотрят: налево, налево, направо, направо.
  3. Поменять $$$a_1$$$ и $$$a_2$$$. В результате последовательность чисел $$$2, 3, 4, 5$$$. Друзья смотрят: направо, направо, направо, направо.