Семья Вовы строит Великую Вовину Стену (название придумано Вовой). Многие поколения внесли свой вклад в ее постройку. Теперь на Вове лежит важное задание завершить ее.
На данный момент стена может быть представлена в виде последовательности \(a\) из \(n\) целых чисел, где \(a_i\) — это высота \(i\)-й части стены.
Вова может класть лишь только кирпичи \(2 \times 1\) в стену (однако их запас у него не ограничен).
Вова может класть кирпичи горизонтально на соседние части стены равной высоты. Это значит, что если для некоторого \(i\) текущая высота части \(i\) равна высоте части \(i + 1\), то Вова может положить туда кирпич и увеличить обе высоты на 1. Очевидно, Вова не может класть кирпичи так, чтобы их части оказывались за границами (левее части \(1\) стены или правее ее части \(n\)).
Следующий абзац есть только в версии 1 задачи.
Вова также может класть кирпичи вертикально. То есть увеличивать высоту любой части стены на 2.
Вова перфекционист, поэтому он считает стену завершенной, когда:
- все части стены имеют одинаковую высоту;
- в стене нет отверстий без кирпичей.
Может ли Вова завершить постройку стены, использовав произвольное количество кирпичей (возможно ноль)?
Выходные данные
Выведите «YES», если Вова может завершить постройку стены, использовав произвольное количество кирпичей (возможно ноль).
В противном случае выведите «NO».
Примечание
В первом примере Вова может положить кирпич на части 2 и 3, чтобы сделать стену \([2, 2, 2, 2, 5]\), а затем положить 3 кирпича на части 1 и 2 и 3 кирпича на части 3 и 4, чтобы сделать ее \([5, 5, 5, 5, 5]\).
Во втором примере Вова может положить кирпич вертикально на часть 3, чтобы сделать стену \([4, 5, 5]\), затем горизонтально на части 2 и 3, чтобы сделать \([4, 6, 6]\), а потом вертикально на часть 1, чтобы сделать \([6, 6, 6]\).
В третьем примере стена уже завершена.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 1 1 2 5
|
YES
|
|
2
|
3
4 5 3
|
YES
|
|
3
|
2
10 10
|
YES
|
|
4
|
3
1 2 3
|
NO
|