И 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
Двигаемся в обратном порядке 2324142 (идём с конца) ей противоположные 1323141
2 задание) ответ: 2949;
мы должны получить 11 и 13 причем минимально . можем только так 9+2 и 9+4 . значит 2949
3 задание) ответ: 3;
чтобы добраться до 21 нам нужно выполнить 1 команду 6 раз и 3 раза вторую , нас спрашивают про вторую пишем ответ 3
4 задание) ответ: 1;
нам нужно число которое делится на 5 то есть 4 отпадает , и также нам нужно чтобы модуль разности был не более 2 и во втором и в третьем модуль разности больше 2 , остается 1.
5 задание) ответ: 1112221;
Я всегда начинаю с обратного
57-56-28-14-7-6-5-4 собираем с конца 1112221
Если число 3306(10) в системе исчисления с основанием а заканчивается цифрой 3, то тогда
число 3303 делится на основание системы а.
Отсюда алгоритм поиска. Находим все делители числа 3303.
3303 = 3*1101 = 3*3*367. Число 367 - простое. Поэтому основаниями системы исчисления
могут быть только 3, 9, 367. Основание =3 не подходит, так как по условию число должно заканчиваться на 3 -> основание больше 3. Остаются 9, 367.