B. Столбы
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перед вами стоят в ряд $$$n$$$ столбов, пронумерованных от $$$1$$$ до $$$n$$$.

Изначально на каждый столб надет ровно один диск. Радиус диска, надетого на $$$i$$$-й столб, равен $$$a_i$$$.

Вы можете перемещать диски с одних столбов на другие. Вы можете взять диск со столба $$$i$$$ и надеть его на столб $$$j$$$, если все следующие условия выполняются:

  1. между столбами $$$i$$$ и $$$j$$$ нет других столбов. Формально, это означает, что $$$|i - j| = 1$$$;
  2. на столб $$$i$$$ надет ровно один диск;
  3. либо столб $$$j$$$ пуст (на нем нет дисков), либо радиус самого верхнего диска на столбе $$$j$$$ строго больше радиуса того диска, который вы перемещаете.

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

Вы можете перемещать диски столько раз, сколько вам нужно, при условии, что все три условия выполняются при каждом вашем действии. Теперь вы хотите узнать, можно ли все $$$n$$$ дисков надеть на один и тот же столб?

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

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

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

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

Выведите YES, если можно все диски надеть на один и тот же столб, или NO, если это не так. Вы можете выводить каждую букву в любом регистре (YES, yes, Yes будут распознаны как положительный ответ, NO, no и nO будут распознаны как отрицательный ответ).

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

В первом примере можно все диски переместить на столб $$$3$$$ при помощи следующих действий:

  1. взять диск с радиусом $$$3$$$ со столба $$$2$$$ и надеть его на столб $$$3$$$;
  2. взять диск с радиусом $$$1$$$ со столба $$$1$$$ и надеть его на столб $$$2$$$;
  3. взять диск с радиусом $$$2$$$ со столба $$$4$$$ и надеть его на столб $$$3$$$;
  4. взять диск с радиусом $$$1$$$ со столба $$$2$$$ и надеть его на столб $$$3$$$.