Задача G. Призы ≡

Условие

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

По итогам конкурса участник может набрать от 2 до N баллов. Если участник наберет K баллов, то он получит один из призов с номером от 1 до K.

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

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

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

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

Первая строка входного файла содержит число N. Вторая строка этого файла содержит N целых чисел: a₁, a₂, …, a_N.

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

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

Ограничения

2 ≤ N ≤ 100000; 1 ≤ a_i ≤ 10⁹

Система оценки и описание подзадач

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

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

N ≤ 100

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

N ≤ 5000

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

N ≤ 100 000

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

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

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

5
1 3 4 2 5

1 3 3 4