Призы
(Время: 1 сек. Память: 16 Мб Сложность: 19%)
Петр участвует в конкурсе, в котором разыгрывается n призов. Призы пронумерованы от 1 до n.
По итогам конкурса участник может набрать от 2 до n баллов. Если участник наберет k баллов, то он получит один из призов с номером от 1 до k. Перед тем, как участник выберет свой приз, ведущий конкурса удаляет один из призов из списка. Затем участник может выбрать любой приз из оставшихся k-1.
Список призов стал известен Петру. Он определил для каждого приза его ценность, для i-го приза она задается целым числом ai.
Требуется написать программу, которая по заданным ценностям призов определяет для каждого k от 2 до n, приз с какой максимальной ценностью гарантированно достанется Петру, если он наберет в конкурсе k баллов.
Входные данные
Первая строка входного файла INPUT.TXT содержит число n (2 ≤ n ≤ 100 000). Вторая строка этого файла содержит n целых чисел: a1, a2, …, an (1 ≤ ai ≤ 109).
Выходные данные
Выходной файл OUTPUT.TXT должен содержать одну строку, содержащую n-1 целых чисел: для каждого k от 2 до n должна быть выведена ценность приза, который достанется Петру, если он наберет k баллов.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
1 3 4 2 5 | 1 3 3 4 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
