Районная олимпиада по информатике 2020 года за 9 класс | Казахстанские олимпиады

Задача E. Второй максимум

Вам дана последовательность $a_1, a_2...a_n$ длины $n$.

Для каждого $k$ от $2$ до $n$ найдите значение второго по величине элемента среди первых $k$ элементов последовательности $a$.

Формат входного файла

В первой строке одно целое число $n$ $(1 <= n <= 10^5)$. Во второй строке $n$ целых чисел $a_1, a_2... a_n$ $(1 <= a_i <= 10^9)$.

Формат выходного файла

Выведите ответ для каждого $k$ от $2$ до $n$.

Примеры

Вход

7
1 2 3 3 7 5 6

Выход

1 2 3 3 5 6