Задача E. Коробки в коробках

Автор:А. Кленин, Р. Данилов   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Юная программистка Алиса подарила юному программисту Васе на день рождения N коробок различных размеров.

Они решили поиграть в игру с коробками.

Алиса раскладывает коробки в произвольном порядке, после чего Вася начинает их складывать друг в друга. Ему разрешено складывать коробку меньшего размера в коробку большего, стоящую рядом слева или справа.

Если в коробке A уже лежат другие коробки, то в нее можно сложить новую коробку только в случае, если её размер меньше всех уже вложенных в A коробок. Иными словами, коробки складываются на манер матрёшек.

Задача Васи — сложить все коробки в одну. Требуется написать программу, которая определит, возможно ли это.

Формат входного файла

Первая строка входного файла содержит целое число N — количество коробок.

Следующая строка содержит N целых чисел ai — размеры коробок. Гарантируется, что все размеры различны.

Формат выходного файла

Выходной файл должен содержать единственную строку 'YES', если существует способ сложить все коробки в одну, либо 'NO' в противном случае.

Ограничения

1 ≤ N ≤ 104

1 ≤ ai ≤ 109

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача Баллы Дополнительные ограничения
Nai
1301 ≤ N ≤ 201 ≤ ai ≤ 100
2301 ≤ N ≤ 2001 ≤ ai ≤ 106
3401 ≤ N ≤ 100001 ≤ ai ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
1 3 2 4
YES
2
5
11 35 50 22 41
NO
3
6
13 5 6 1 2 3
YES

0.042s 0.008s 15