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

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

Ограничение по времени Ограничение по памяти
1 секунда 256 мегабайт

Вам дана последовательность a1,a2...ana_1, a_2...a_n длины nn.

Для каждого kk от 22 до nn найдите значение второго по величине элемента среди первых kk элементов последовательности aa.

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

В первой строке одно целое число nn (1<=n<=105)(1 <= n <= 10^5). Во второй строке nn целых чисел a1,a2...ana_1, a_2... a_n (1<=ai<=109)(1 <= a_i <= 10^9).

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

Выведите ответ для каждого kk от 22 до nn.

Примеры

Вход

7
1 2 3 3 7 5 6

Выход

1 2 3 3 5 6