D2. Великая Вовина Стена (Версия 2)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Семья Вовы строит Великую Вовину Стену (название придумано Вовой). Многие поколения внесли свой вклад в ее постройку. Теперь на Вове лежит важное задание завершить ее.

На данный момент стена может быть представлена в виде последовательности $$$a$$$ из $$$n$$$ целых чисел, где $$$a_i$$$ — это высота $$$i$$$-й части стены.

Вова может класть лишь только кирпичи $$$2 \times 1$$$ в стену (однако их запас у него не ограничен).

Вова может класть кирпичи только горизонтально на соседние части стены равной высоты. Это значит, что если для некоторого $$$i$$$ текущая высота части $$$i$$$ равна высоте части $$$i + 1$$$, то Вова может положить туда кирпич и увеличить обе высоты на 1. Очевидно, Вова не может класть кирпичи так, чтобы их части оказывались за границами (левее части $$$1$$$ стены или правее ее части $$$n$$$).

Обратите внимание, что Вова не может класть кирпичи вертикально.

Вова перфекционист, поэтому он считает стену завершенной, когда:

  • все части стены имеют одинаковую высоту;
  • в стене нет отверстий без кирпичей.

Может ли Вова завершить постройку стены, использовав произвольное количество кирпичей (возможно ноль)?

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

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество частей стены.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — начальные высоты частей стены.

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

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

В противном случае выведите «NO».

Примеры
Входные данные
5
2 1 1 2 5
Выходные данные
YES
Входные данные
3
4 5 3
Выходные данные
NO
Входные данные
2
10 10
Выходные данные
YES
Примечание

В первом примере Вова может положить кирпич на части 2 и 3, чтобы сделать стену $$$[2, 2, 2, 2, 5]$$$, а затем положить 3 кирпича на части 1 и 2 и 3 кирпича на части 3 и 4, чтобы сделать ее $$$[5, 5, 5, 5, 5]$$$.

Во втором примере Вова не может положить кирпичей в стену.

В третьем примере стена уже завершена.