C2. Небоскрёбы (усложнённая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это более сложная версия задачи. В этой версии $$$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$$$ ($$$1 \leq n \leq 500\,000$$$) — количество участков.

Вторая строка содержит целые числа $$$m_1, m_2, \ldots, m_n$$$ ($$$1 \leq m_i \leq 10^9$$$) —максимально возможное количество этажей для небоскрёба на каждом участке.

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

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

Если возможно несколько ответов, выведите любой.

Примеры
Входные данные
5
1 2 3 2 1
Выходные данные
1 2 3 2 1 
Входные данные
3
10 6 8
Выходные данные
10 6 6 
Примечание

В первом примере можно построить все небоскрёбы с максимально возможной высотой.

Во втором примере придать максимальную высоту всем небоскрёбам нельзя, так как это нарушает ограничение дизайн-кода. Ответ $$$[10, 6, 6]$$$ является оптимальным. Обратите внимание, что ответ $$$[6, 6, 8]$$$ также удовлетворяет всем ограничениям, но оптимальным не является.