Майк — президент страны What-The-Fatherland. Помимо Майка, там живёт ещё n медведей. Все они стоят в ряд и пронумерованы от 1 до n слева направо. Рост i-го медведя составляет ровно ai футов.
Назовём группой медеведей непустой непрерывный подотрезок этого ряда. Размер группы — это количество медведей в этой группе. Сила группы — это минимальная высота медведя в этой группе.
Майку хочется знать для каждого x, такого что 1 ≤ x ≤ n, максимальную силу группы медведей размера x.
Выходные данные
Выведите n целых чисел в одной строке. Для каждого x от 1 до n выведите максимальную силу среди всех групп размера x.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
1 2 3 4 5 4 3 2 1 6
|
6 4 4 3 3 2 2 1 1 1
|