У AquaMoon есть \(n\) друзей. Они встали в ряд. \(i\)-й слева друг надел футболку с числом \(a_i\), написанным на ней. Каждый друг смотрит в одну из двух сторон налево или направо. В начале все друзья смотрят направо.
AquaMoon может делать операции с друзьями. На каждой операции AquaMoon может выбрать два соседних в ряду друга и поменять их местами. После каждой операции оба друга изменяют направление, в котором смотрели, на противоположное: если кто-то смотрел налево, он будет смотреть направо, и наоборот.
AquaMoon надеется, что после нескольких операций числа, написанные на футболках у \(n\) друзей станут неубывающими, если смотреть на них слева направо. Также она хочет, чтобы в этот момент все друзья смотрели направо. Установите, возможно ли это.
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если существует возможная последовательность операций; иначе, выведите «NO» (без кавычек).
Вы можете выводить каждую букву в любом регистре (строчную или заглавную).
Примечание
Возможная последовательность операций для первого набора входных данных:
- Поменять \(a_1\) и \(a_2\). В результате последовательность чисел \(3, 4, 2, 5\). Друзья смотрят: налево, налево, направо, направо.
- Поменять \(a_2\) и \(a_3\). В результате последовательность чисел \(3, 2, 4, 5\). Друзья смотрят: налево, налево, направо, направо.
- Поменять \(a_1\) и \(a_2\). В результате последовательность чисел \(2, 3, 4, 5\). Друзья смотрят: направо, направо, направо, направо.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
4 3 2 5
4
3 3 2 2
5
1 2 3 5 4
|
YES
YES
NO
|