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

Вам дан массив $$$a_1, a_2, \dots, a_n$$$. Вы можете выполнять операции с массивом. За одну операцию вы можете выбрать целое число $$$i$$$ ($$$1 \le i < n$$$) и поменять местами $$$a_i$$$ и $$$a_{i+1}$$$ в массиве, если $$$a_i + a_{i+1}$$$ нечётно.

Определите, можно ли его отсортировать в неубывающем порядке, используя эти операции любое количество раз.

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

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

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

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

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

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

Для каждого набора входных данных выведите «Yes» или «No» в зависимости от того, можете ли вы или нет отсортировать данный массив.

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

Пример
Входные данные
4
4
1 6 31 14
2
4 2
5
2 9 6 7 10
3
6 6 6
Выходные данные
Yes
No
No
Yes
Примечание

В первом наборе входных данных мы можем просто поменять местами $$$31$$$ и $$$14$$$ ($$$31 + 14 = 45$$$, что нечётно) и получить неубывающий массив $$$[1,6,14,31]$$$.

Во втором наборе входных данных единственным способом отсортировать массив является поменять местами $$$4$$$ и $$$2$$$, но это невозможно, поскольку их сумма $$$4 + 2 = 6$$$ является чётной.

В третьем наборе входных данных мы не можем сделать последовательность неубывающей.

В четвёртом наборе входных данных массив уже является неубывающим.