Во время уборки побережья Алиса нашла \(n\) кучек камней. В \(i\)-й кучке было \(a_i\) камней.
Кучки \(i\) и \(i + 1\) являются соседними для всех \(1 \leq i \leq n - 1\). Если кучка \(i\) стала пустой, кучки \(i - 1\) и \(i + 1\) не становятся соседними.
Алиса не хочет сама убирать эти кучки, поэтому она поручила задачу Вам. Она разрешила убирать камни только выполняя следующую операцию:
- Выбрать две соседних кучки с ненулевым количеством камней, и удалить по одному камню из каждой из них.
Так как это не всегда возможно, Алиса разрешила Вам применить следующую суперспособность:
- До начала уборки выбрать две соседние кучки и поменять их местами.
Определите, возможно ли убрать все камни, использовав суперспособность не более одного раза.
Выходные данные
Для каждого набора входных данных, выведите YES или NO — возможно ли убрать все камни, использовав суперспособность не более одного раза.
Примечание
В первом наборе входных данных, можно убрать все камни, не применяя суперспособность: \([1, 2, 1] \rightarrow [1, 1, 0] \rightarrow [0, 0, 0]\).
Во втором наборе можно применить суперспособность ко второй и третьей кучкам, получив первый тестовый случай.
В третьем наборе можно применить суперспособность ко четвёртой и пятой кучкам, получив \(a = [2, 2, 2, 3, 1]\).
В четвёртом наборе можно применить суперспособность к первой и второй кучкам, получив \(a = [1900, 2100, 1600, 3000, 1600]\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
1 2 1
3
1 1 2
5
2 2 2 1 3
5
2100 1900 1600 3000 1600
2
2443 2445
|
YES
YES
YES
YES
NO
|