| The 2026 ICPC Belarus Qualification |
|---|
| Закончено |
Светозар — тоже программист, но он пишет код на магических языках программирования.
Сегодня у него в программе есть массив $$$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 в противном случае. Выводить слова можно в любом регистре.
441 6 3 233 1 214252 4 6 8 10
NONOYESYES
34-3 2 -1 41-10000000004-5 -7 0 2
YESYESNO
Рассмотрим второй пример. В первом тестовом случае достаточно поменять два соседних числа $$$2$$$ и $$$-1$$$, чтобы массив оказался упорядоченным.
Во втором тестовом случае массив уже упорядочен, менять ничего не нужно.
В третьем тестовом случае можно показать, что упорядочить массив обменами соседних чисел, соблюдая правила, не удастся.
| Название |
|---|


