У вас есть массив \(a\), состоящий из \(n\) целых чисел. К заданному массиву можно применять следующую операцию:
- Поменять местами два элемента \(a_i\) и \(a_j\) такие, что \(i \neq j\), \(a_i\) и \(a_j\) либо оба четные, либо оба нечетные.
Определите, можно ли, совершая операцию некоторое число раз (возможно, нулевое), отсортировать массив в порядке неубывания?
Например, пусть \(a\) = [\(7, 10, 1, 3, 2\)]. Тогда можно совершить \(3\) операции для того, чтобы отсортировать массив:
- Поменять местами \(a_3 = 1\) и \(a_1 = 7\), так как \(1\) и \(7\) — нечетные. Получим \(a\) = [\(1, 10, 7, 3, 2\)];
- Поменять местами \(a_2 = 10\) и \(a_5 = 2\), так как \(10\) и \(2\) — четные. Получим \(a\) = [\(1, 2, 7, 3, 10\)];
- Поменять местами \(a_4 = 3\) и \(a_3 = 7\), так как \(3\) и \(7\) — нечетные. Получим \(a\) = [\(1, 2, 3, 7, 10\)].
Выходные данные
Для каждого набора входных данных в отдельной строке выведите:
- «YES», если массив можно отсортировать, применив к нему операцию некоторое количество раз;
- «NO» в противном случае.
Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
Примечание
Первый набор входных данных разобран в условии задачи.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5
7 10 1 3 2
4
11 9 3 5
5
11 3 15 3 2
6
10 7 8 1 2 3
1
10
5
6 6 4 1 6
|
YES
YES
NO
NO
YES
NO
|