Remote Training on Programming

Петр участвует в конкурсе, в котором разыгрывается n призов. Призы пронумерованы от 1 до n.

По итогам конкурса участник может набрать от 2 до n баллов. Если участник наберет k баллов, то он получит один из призов с номером от 1 до k. Перед тем, как участник выберет свой приз, ведущий конкурса удаляет один из призов из списка. Затем участник может выбрать любой приз из оставшихся k – 1.

Список призов стал известен Петру. Он определил для каждого приза его ценность, для i-го приза она задается целым числом a_i.

Требуется написать программу, которая по заданным ценностям призов определяет для каждого k от 2 до n, приз с какой максимальной ценностью гарантированно достанется Петру, если он наберет в конкурсе k баллов.

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

Первая строка входного файла содержит число n (2 ≤ n ≤ 100 000). Вторая строка этого файла содержит n целых чисел: a₁, a₂, …, a_n (1 ≤ a_i ≤ 10⁹).

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

Выходной файл должен содержать одну строку, содержащую n – 1 целых чисел: для каждого k от 2 до n должна быть выведена ценность приза, который достанется Петру, если он наберет k баллов.

 

Пример входных и выходных файлов

Входные данные	Выходные данные
5 1 3 4 2 5	1 3 3 4

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

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

Подзадача 1 (24 балла)

n ≤ 100

Подзадача 2 (24 балла)

n ≤ 5000

Подзадача 3 (52 балла)

n ≤ 100 000

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.