B. Майк и футы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Майк — президент страны What-The-Fatherland. Помимо Майка, там живёт ещё n медведей. Все они стоят в ряд и пронумерованы от 1 до n слева направо. Рост i-го медведя составляет ровно ai футов.

Назовём группой медеведей непустой непрерывный подотрезок этого ряда. Размер группы — это количество медведей в этой группе. Сила группы — это минимальная высота медведя в этой группе.

Майку хочется знать для каждого x, такого что 1 ≤ x ≤ n, максимальную силу группы медведей размера x.

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

В первой строке ввода записано целое число n (1 ≤ n ≤ 2 × 105), количество медведей.

Во второй строке записано n целых чисел, разделенных пробелом, a1, a2, ..., an (1 ≤ ai ≤ 109) — высоты медведей.

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

Выведите n целых чисел в одной строке. Для каждого x от 1 до n выведите максимальную силу среди всех групп размера x.

Примеры
Входные данные
10
1 2 3 4 5 4 3 2 1 6
Выходные данные
6 4 4 3 3 2 2 1 1 1