Олимпиады для начинающих: Московская олимпиада, 7-8 класс, 2020 год

Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .

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

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

Более формально, пронумеруем участки целыми числами от \(1\) до \(n\). Тогда у небоскрёба на участке с номером \(i\) количество этажей \(a_i\) не может быть запланировано больше \(m_i\), и также не может быть, что на плане существуют два участка с номерами \(j\) и \(k\) таких, что \(j \lt i \lt k\), и \(a_j \gt a_i \lt a_k\).

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