C++

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

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

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

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

формат входных данных

первая строка входного файла содержит число n (2≤n≤1). вторая строка этого файла содержит n целых чисел: a1, a2, an (1≤ai≤109).

формат выходных данных

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

входные данные

5

1 3 4 2 5

выходные данные

1 3 3 4