Задача №113096. Призы(2016)
Петя участвует в конкурсе, в котором разыгрывается \(n\) призов. Призы пронумерованы от 1 до \(n\).
По итогам конкурса участник может набрать от 2 до \(n\) баллов. Если участник наберет \(k\) баллов, то он получит один из призов с номером от 1 до \(k\). Перед тем, как участник выберет свой приз, ведущий конкурса удаляет один из призов из списка. Затем участник может выбрать любой приз из оставшихся \(k\) – 1.
Список призов стал известен Пете. Петя определил для каждого приза его ценность, для \(i\)-го приза она задается целым числом \(a_i\) .
Требуется написать программу, которая по заданным ценностям призов определяет для каждого \(k\) от 2 до \(n\), приз с какой максимальной ценностью гарантированно достанется Пете, если он наберет в конкурсе \(k\) баллов.
Первая строка входного файла содержит число \(n\) (\(2 \le n \le 100 000\)). Вторая строка этого файла содержит n целых чисел: \(a_1, a_2, …, a_n\) (\(1 \le a_i ≤ 10^9\) ).
Выходной файл должен содержать одну строку, содержащую \(n\) – 1 целых чисел: для каждого \(k\) от 2 до \(n\) должна быть выведена ценность приза, который достанется Пете, если он наберет \(k\) баллов.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
\(n \le 100\)
\(n \le 5000\)
\(n \le 100000\)
5 1 3 4 2 5
1 3 3 4