У Ярослава есть массив, состоящий из n целых чисел. За одну секунду Ярослав может поменять местами два рядом стоящих элемента массива. Сейчас Ярослава интересует вопрос: может ли он за конечное время получить массив, в котором любые два соседних элемента различны?
Помогите Ярославу.
Выходные данные
В единственную строку выведите «YES» (без кавычек), если Ярослав может получить нужный ему массив, и «NO» (без кавычек) в противном случае.
Примечание
В первом примере изначальный массив подходит.
Во втором примере Ярослав может получить массив: 1, 2, 1. Для этого он может поменять два последних элемента массива местами.
В третьем примере Ярослав не может получить нужный массив.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
1
|
YES
|
|
2
|
3
1 1 2
|
YES
|
|
3
|
4
7 7 7 7
|
NO
|