F. Ящики
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп приехал на склад с ящиками. Он выстроил все ящики в $$$n$$$ стопок, в каждой из стопок ящики стоят друг на друге.

После этого он захотел перераспределить ящики. Для этого он решил сделать еще $$$n - 1$$$ стопку, причем каждая новая стопка должна быть между двумя стопками, которые были изначально. При этом между каждой соседней парой изначальных стопок должна быть ровно одна новая. Каждая новая стопка изначально пустая, то есть в ней нет ни одного ящика.

Таким образом, слева и справа от изначальных стопок появится по одной новой стопке, за исключением самой левой изначальной стопки (у нее будет только одна новая стопка справа) и самой правой изначальной стопки (у нее будет только одна новая стопка слева).

Поликарп будет перераспределять ящики следующим образом. Он может брать ящики только из изначальных стопок и перемещать их только в новые соседние стопки с той, из которой он берет ящики.

Перед вами стоит задача определить, возможно ли перераспределить ящики таким образом, чтобы в каждой из $$$2\cdot n - 1$$$ стопок было одинаковое количество ящиков. Ящики запрещено выкидывать или добавлять, то есть Поликарп должен перераспределить именно те ящики, которые были в $$$n$$$ изначальных стопках.

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

В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество изначальных стопок.

Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 1\,000$$$), где $$$a_i$$$ равно количеству ящиков в $$$i$$$-й изначальной стопке.

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

Если невозможно перераспределить ящики описанным образом, выведите «NO» (без кавычек).

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

Примеры
Входные данные
3
7 13 5
Выходные данные
YES
Входные данные
2
30 10
Выходные данные
NO
Входные данные
6
8 16 13 18 12 10
Выходные данные
YES
Входные данные
3
11 5 9
Выходные данные
NO
Примечание

В первом примере после добавления двух новых стопок, последовательность количества ящиков в стопках (обозначим ее как $$$a$$$) равна $$$[7, 0, 13, 0, 5]$$$. После этого можно взять два ящика из первой стопки и положить во вторую. После этого $$$a = [5, 2, 13, 0, 5]$$$. Затем можно взять $$$5$$$ ящиков из третьей стопки и положить в четвертую. После этого $$$a = [5, 2, 8, 5, 5]$$$. После этого можно взять $$$3$$$ ящика из третьей стопки и положить во вторую. После этого $$$a = [5, 5, 5, 5, 5]$$$. Таким образом, Поликарп может сделать количество ящиков во всех стопках одинаковым.

Во втором примере невозможно перераспределить ящики между тремя стопками так, чтобы во всех стопках было одинаковое количество ящиков.