Это более сложная версия задачи. В этой версии \(n \le 500\,000\)
В Берляндии активно застраивается окраина столицы. Компания «Kernel Panic» руководит постройкой жилого комплекса из небоскрёбов в Новой Берлскве. Все небоскрёбы строятся вдоль шоссе. Известно, что компания уже купила \(n\) участков возле шоссе и готовится возвести \(n\) небоскрёбов, по одному зданию на один участок.
Архитекторы при планировании зданий должны учитывать несколько требований. Во-первых, поскольку земля на каждом участке имеет разные свойства, для каждого небоскрёба есть свое ограничение по количеству этажей, которое он может иметь. Во-вторых, согласно дизайн-коду города, недопустима ситуация, когда для какого-то небоскрёба сразу по обе стороны от него есть небоскрёбы выше него.
Более формально, пронумеруем участки целыми числами от \(1\) до \(n\). Тогда у небоскрёба на участке с номером \(i\) количество этажей \(a_i\) не может быть больше \(m_i\) (\(1 \le a_i \le m_i\)). Также не может быть, что на плане существуют два участка с номерами \(j\) и \(k\), таких что \(j < i < k\) и \(a_j > a_i < a_k\). Участки \(j\) и \(k\) не обязаны быть соседними с \(i\).
Компания хочет, чтобы суммарное количество этажей в построенных небоскрёбах было как можно больше. Помогите ей выбрать количество этажей для каждого небоскрёба оптимальным образом, то есть так, чтобы выполнялись все ограничения, а среди всех таких вариантов выберите один из планов, в котором суммарное количество этажей максимально возможно.
Выходные данные
Выведите \(n\) чисел \(a_i\) — количества этажей в плане для каждого небоскрёба, такие, что выполняются все ограничения, а суммарное количество этажей во всех небоскрёбах максимально возможное.
Если возможно несколько ответов, выведите любой.
Примечание
В первом примере можно построить все небоскрёбы с максимально возможной высотой.
Во втором примере придать максимальную высоту всем небоскрёбам нельзя, так как это нарушает ограничение дизайн-кода. Ответ \([10, 6, 6]\) является оптимальным. Обратите внимание, что ответ \([6, 6, 8]\) также удовлетворяет всем ограничениям, но оптимальным не является.