И 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
{данная программа переводит любое сочетание символов ascii в систему счисления заданную пользователем.}
//pascal abc.net v3.0 сборка 1111
var
a,i,b,r,n,j,bug: integer;
s,se,slo,slof: string;
procedure preob(var a,b,n: integer; var se: string);
begin
repeat
b: =a mod n;
a: =a div n;
str(b,se);
s+=se;
until (a< =n-1);
end;
beginreadln(slo);
readln(n);
for j: =1 to length(slo) do
begin;
a: =ord(slo[j]);
preob(a,b,n,se);
str(a,se);
s+=se;
for i: =1 to length(s) div 2 do
begin;
se: =s[i];
s[i]: =s[length(s)-i+1];
s[length(s)-i+1]: =se[1];
end;
write(s,'-');
slof: =slof+s;
delete(s,1,length(s));
end;
end.
пример ввода:
работа на завтра.
2
пример вывода:
11000100-11101110-11101100-11100000-11111000-11101101-11111111-11111111-100000-11110000-11100000-11100001-11101110-11110010-11100000-100000-11101101-11100000-100000-11100111-11100000-11100010-11110010-11110000-11100000-101110-
{таким образом, фразу " работа на завтра." можно закодировать как "11000100-11101110-11101100-11100000-11111000-11101101-11111111-11111111-100000-11110000-11100000-11100001-11101110-11110010-11100000-100000-11101101-11100000-100000-11100111-11100000-11100010-11110010-11110000-11100000-101110-".}