| Автор: | А. Кленин, Р. Данилов | Ограничение времени: | 3 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 100 |
Юная программистка Алиса подарила юному программисту Васе на день рождения N коробок различных размеров.
Они решили поиграть в игру с коробками.
Алиса раскладывает коробки в произвольном порядке, после чего Вася начинает их складывать друг в друга. Ему разрешено складывать коробку меньшего размера в коробку большего, стоящую рядом слева или справа.
Если в коробке A уже лежат другие коробки, то в нее можно сложить новую коробку только в случае, если её размер меньше всех уже вложенных в A коробок. Иными словами, коробки складываются на манер матрёшек.
Задача Васи — сложить все коробки в одну. Требуется написать программу, которая определит, возможно ли это.
Первая строка входного файла содержит целое число N — количество коробок.
Следующая строка содержит N целых чисел ai — размеры коробок. Гарантируется, что все размеры различны.
Выходной файл должен содержать единственную строку 'YES', если существует способ сложить все коробки в одну, либо 'NO' в противном случае.
1 ≤ N ≤ 104
1 ≤ ai ≤ 109
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | ||
|---|---|---|---|---|
| N | ai | |||
| 1 | 30 | 1 ≤ N ≤ 20 | 1 ≤ ai ≤ 100 | |
| 2 | 30 | 1 ≤ N ≤ 200 | 1 ≤ ai ≤ 106 | |
| 3 | 40 | 1 ≤ N ≤ 10000 | 1 ≤ ai ≤ 109 | |
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|
| 3 |
|
|