Это более сложная версия задачи. В этой версии $$$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$$$.

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