A. Ярослав и перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Ярослава есть массив, состоящий из n целых чисел. За одну секунду Ярослав может поменять местами два рядом стоящих элемента массива. Сейчас Ярослава интересует вопрос: может ли он за конечное время получить массив, в котором любые два соседних элемента различны?

Помогите Ярославу.

Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 100) — количество элементов в массиве. Во второй строке содержится n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 1000) — элементы массива.

Выходные данные

В единственную строку выведите «YES» (без кавычек), если Ярослав может получить нужный ему массив, и «NO» (без кавычек) в противном случае.

Примеры
Входные данные
1
1
Выходные данные
YES
Входные данные
3
1 1 2
Выходные данные
YES
Входные данные
4
7 7 7 7
Выходные данные
NO
Примечание

В первом примере изначальный массив подходит.

Во втором примере Ярослав может получить массив: 1, 2, 1. Для этого он может поменять два последних элемента массива местами.

В третьем примере Ярослав не может получить нужный массив.