Вам дан массив \(a_1, a_2, \dots, a_n\). Вы можете выполнять операции с массивом. За одну операцию вы можете выбрать целое число \(i\) (\(1 \le i < n\)) и поменять местами \(a_i\) и \(a_{i+1}\) в массиве, если \(a_i + a_{i+1}\) нечётно.
Определите, можно ли его отсортировать в неубывающем порядке, используя эти операции любое количество раз.
Выходные данные
Для каждого набора входных данных выведите «Yes» или «No» в зависимости от того, можете ли вы или нет отсортировать данный массив.
Вы можете выводить каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).
Примечание
В первом наборе входных данных мы можем просто поменять местами \(31\) и \(14\) (\(31 + 14 = 45\), что нечётно) и получить неубывающий массив \([1,6,14,31]\).
Во втором наборе входных данных единственным способом отсортировать массив является поменять местами \(4\) и \(2\), но это невозможно, поскольку их сумма \(4 + 2 = 6\) является чётной.
В третьем наборе входных данных мы не можем сделать последовательность неубывающей.
В четвёртом наборе входных данных массив уже является неубывающим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
1 6 31 14
2
4 2
5
2 9 6 7 10
3
6 6 6
|
Yes
No
No
Yes
|