Задача Конкурс прошу помочь

Аня и Яна участвуют в одной команде в конкурсе, в котором разыгрывается n призов, пронумерованных от 1 до n.

Команда может набрать в конкурсе от 2 до n баллов. При этом, если команда набрала k баллов, то каждый из ее участников может выбрать любой из призов с номерами от 1 до k. Яна, как капитан команды, первая выберет один из этих k призов, а затем Аня выберет себе приз из k−1 оставшихся.

Для каждого из n призов Аня определила, насколько он для нее ценный: ценность i-го приза для Ани задается целым числом ai.

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

Формат входных данных
В первой строке вводится натуральное число
n (2≤n≤100000) – количество призов. Во второй строке вводятся n целых чисел a1,a2,...,an (1≤ai≤10^9) – значения ценности призов для Ани.

Формат результата
Требуется вывести строку, содержащую n−1 целых чисел: для каждого k от 2 до n необходимо вывести минимальную ценность приза, который гарантировано получит Аня, если команда наберет k баллов.

Тема Линейный поиск в списках и матрицах