Задача "Небоскребы"

Небоскрёбы
В Берляндии активно застраивается окраина столицы. Компания "Kernel Panic" руководит постройкой жилого комплекса из небоскрёбов в Новой Берлскве. Все небоскрёбы строятся вдоль шоссе. Известно, что компания уже купила n участков возле шоссе и готовится возводить небоскрёбы, по одному зданию на один участок.

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

Более формально, пронумеруем участки целыми числами от 1 до n. Тогда у небоскрёба на участке с номером i количество этажей ai не может быть запланировано больше mi, и также не может быть, что на плане существуют два участка с номерами j и k таких, что j<i<k, и aj>ai<ak.

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

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

В первой строке задано одно целое число n (1≤n≤500 000) — количество участков.

Вторая строка содержит n целых чисел. i-е число задает значение mi (1≤mi≤109) — максимально возможное количество этажей для небоскрёба на участке i.

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

Выведите n чисел ai — количества этажей в плане для каждого небоскрёба, такие, что выполняются все ограничения, а суммарное количество этажей во всех небоскрёбах максимально возможное. Если возможных ответов несколько, выведите любой.

Ограничения
Время выполнения: 3 секунды

0