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