Саша Белый недавно устроился подрабатывать на горнолыжный курорт недалеко от Аши. Первым делом ему поручили установить ограждения для лыжной трассы.
Саше дали n ограждений, каждое длиной a
i. Любые два последовательных ограждения скреплены друг с другом, но при этом могут произвольно поворачиваться друг относительно друга.
Саша хочет сделать трассу интересной: по его мнению, трасса должна быть в форме спирали (ограждение под номером i +1 должно быть повернуто на 90 градусов по часовой стрелке относительно ограждения под номером i; при этом никакие ограждения, кроме смежных, не должны касаться друг друга и пересекаться).
К сожалению, не из любых наборов ограждений можно сложить спираль. Помогите Саше для заданного набора определить, возможно ли из него составить спираль.
Входные данные
В первой строке входных данных записано целое число n — количество ограждений (1 <= n <= 10
5). Во второй строке через пробел заданы n целых чисел a
i — длина i-го ограждения (1 <= a
i <=10
9).
Выходные данные
Выведите YES, если возможно из данных ограждений сложить спираль, или NO в противном случае.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
1 2 3 3 5 |
YES |
| 2 |
6
5 7 6 8 6 10 |
NO |
| 3 |
9
1 1 2 2 6 2 2 1 1 |
YES |
Замечание
Обратите внимание на третий пример, спираль может иметь два центра, главное, чтобы ограждения не пересекались. Иллюстрация к третьему примеру:
