Рабочее место участника

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

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

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

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

Первая строка входного файла содержит число `n` (`2 ≤ n ≤ 100 000`). Вторая строка этого файла содержит `n` целых чисел: `a_1,\ a_2,\ …,\ a_n` (`1\ ≤\ a_i\ ≤\ 10^9`).

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

5
1 3 4 2 5

1 3 3 4

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

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