Хетаг решил отвлечься от работы и собрать друзей поиграть в настольный теннис. У Хетага ровно n−1
друг, и по счастливой случайности все они просто обожают настольный теннис.

Есть только две проблемы. Во-первых, на всех n
человек у них только один теннисный стол. Во-вторых, все они — программисты, и играют по алгоритму, к которому все давно привыкли. Как это часто бывает со старым кодом, никто не понимает почему он так устроен и кто его написал, но исправлять что-то уже поздно. Так и здесь — система, по которой они играют, вызывает некоторые сомнения, но что поделать. Алгоритм игры заключается в следующем: два первых человека играют между собой, тогда как оставшиеся образуют очередь; после игры выигравший остается у стола, проигравшего заменяет первый человек из очереди, а сам проигравший встает в ее конец.

При этом известно, что у игрока, стоящего изначально на i
-м месте в очереди, сила равна ai
, а игрок с большей силой всегда побеждает игрока с меньшей. Силы любых двух игроков различны. Считайте, что изначально к столу подходят первые два человека из очереди, а затем применяется описанная выше система.

Друзья считают проведенный турнир удачным, если в какой-то момент каждый сыграет с каждым. Помогите им, зная силы всех игроков, определить будет турнир удачным или нет.

Входные данные
В первой строке содержится целое число n
— суммарное количество игроков (2⩽n⩽105
).
В следующей строке через пробел перечислены n
чисел ai — силы игроков в порядке их следования в очереди (1⩽ai⩽109
).

Выходные данные
Выведите «YES» (без кавычек), если в таком турнире в какой-то момент каждый сыграет с каждым хотя бы по одному разу, и «NO» в обратном случае.