Небоскребы

Небоскрёбы
В Берляндии активно застраивается окраина столицы. Компания "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 — количества этажей в плане для каждого небоскрёба такие, что выполняются все ограничения, а суммарное количество этажей во всех небоскрёбах максимально возможное. Если возможных ответов несколько, выведите любой.

Примеры
Ввод 1
5
1 2 3 2 1
Вывод
1 2 3 2 1

О(n)

0

Небоскрёбы
Небоскрёбы
https://www.cyberforum.ru/pyth... 69313.html
Небоскрёбы

1

Конечно спасибо за ресурсы,но информация в них про динамику... А не линейные алгоритмы.

0