| Codeforces Round 305 (Div. 1) |
|---|
| Закончено |
Майк — президент страны 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
