Вам дан массив $$$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$$$ является чётной.
В третьем наборе входных данных мы не можем сделать последовательность неубывающей.
В четвёртом наборе входных данных массив уже является неубывающим.
| Codeforces Round 771 (Div. 2) |
|---|
| Закончено |
