И 250 РУБЛЕЙ Петя участвует в конкурсе, в котором разыгрывается n призов. Призы пронумерованы от 1 до n. По итогам конкурса участник может набрать от 2 до n . Если участник наберет k , то он получит один из призов с номером от 1 до k. Перед тем, как участник выберет свой приз, ведущий конкурса удаляет один из призов из списка. Затем участник может выбрать любой приз из оставшихся k – 1. Список призов стал известен Пете. Петя определил для каждого приза его ценность, для i-го приза она задается целым числом ai . Требуется написать программу, которая по заданным ценностям призов определяет для каждого k от 2 до n, приз с какой максимальной ценностью гарантированно достанется Пете, если он наберет в конкурсе k . Входные данные Первая строка входного файла содержит число n (2≤n≤100000 Вторая строка этого файла содержит n целых чисел: a1, a2, …, an (1≤ai≤109 ). Выходные данные Выходной файл должен содержать одну строку, содержащую n – 1 целых чисел: для каждого k от 2 до n должна быть выведена ценность приза, который достанется Пете, если он наберет k . Описание подзадач и системы оценивания за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены. Подзадача 1 ( ) n≤100 Подзадача 2 ( ) n≤5000 Подзадача 3 ( ) n≤100000 Примеры входные данные 5 1 3 4 2 5 выходные данные 1 3 3 4