E. Магический массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Светозар — тоже программист, но он пишет код на магических языках программирования.

Сегодня у него в программе есть массив $$$a$$$, состоящий из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$. Светозар хочет его упорядочить по неубыванию, то есть сделать каждое следующее число в массиве не меньше предыдущего.

Магия языка программирования пока неподвластна Светозару, поэтому он может делать только операции следующего вида: поменять местами два каких-нибудь соседних элемента $$$a_i$$$ и $$$a_{i+1}$$$, но только в том случае, когда их сумма нечётна. Данную операцию можно применять любое (в том числе нулевое) количество раз. Если Светозар попытается поменять другие пары чисел, у него это не получится.

Определите, может ли Светозар упорядочить массив, или его способностей для этого не хватит.

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

Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \leqslant t \leqslant 2 \cdot 10^5$$$) — количество тестовых случаев. Далее следуют $$$t$$$ описаний тестовых случаев.

Первая строка описания содержит целое число $$$n$$$ ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$) — длину массива.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$-10^9 \leqslant a_i \leqslant 10^9$$$) — элементы массива.

Гарантируется, что сумма значений $$$n$$$ в одном входном файле не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого тестового случая выведите в отдельной строке YES, если массив можно сделать неубывающим, или NO в противном случае. Выводить слова можно в любом регистре.

Примеры
Входные данные
4
4
1 6 3 2
3
3 1 2
1
42
5
2 4 6 8 10
Выходные данные
NO
NO
YES
YES
Входные данные
3
4
-3 2 -1 4
1
-1000000000
4
-5 -7 0 2
Выходные данные
YES
YES
NO
Примечание

Рассмотрим второй пример. В первом тестовом случае достаточно поменять два соседних числа $$$2$$$ и $$$-1$$$, чтобы массив оказался упорядоченным.

Во втором тестовом случае массив уже упорядочен, менять ничего не нужно.

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