Система рекордов получает результаты участников по порядку. После каждого нового результата на табло должен отображаться наибольший результат среди всех уже полученных к этому моменту.

Дана последовательность из n целых чисел, где i-е число — результат, поступивший в систему на i-м шаге. Для каждого шага выведите значение, которое будет показано на табло после обработки этого результата.

Иными словами, для каждой позиции нужно вывести максимум среди всех элементов от начала последовательности до этой позиции включительно.

Входные данные

В первой строке задано число n (1 <= n <= 2*10^5).

Во второй строке заданы n целых чисел a_i (-10^9 <= a_i <= 10^9).

Выходные данные

Выведите n чисел через пробел — значения, которые система рекордов будет показывать после каждого шага.

Ограничения

1 <= n <= 2*10^5

-10^9 <= a_i <= 10^9

Примеры

Пример 1

Входные данные

1
0

Выходные данные

0

Пример 2

Входные данные

5
3 1 4 1 5

Выходные данные

3 3 4 4 5