CF1313C2.Skyscrapers (hard version)

This is a harder version of the problem. In this version $n \le 500\,000$

The outskirts of the capital are being actively built up in Berland. The company "Kernel Panic" manages the construction of a residential complex of skyscrapers in New Berlskva. All skyscrapers are built along the highway. It is known that the company has already bought $n$ plots along the highway and is preparing to build $n$ skyscrapers, one skyscraper per plot.

Architects must consider several requirements when planning a skyscraper. Firstly, since the land on each plot has different properties, each skyscraper has a limit on the largest number of floors it can have. Secondly, according to the design code of the city, it is unacceptable for a skyscraper to simultaneously have higher skyscrapers both to the left and to the right of it.

Formally, let's number the plots from $1$ to $n$. Then if the skyscraper on the $i$-th plot has $a_i$ floors, it must hold that $a_i$ is at most $m_i$ ($1 \le a_i \le m_i$). Also there mustn't be integers $j$ and $k$ such that $j \lt i \lt k$ and $a_j \gt a_i \lt a_k$. Plots $j$ and $k$ are not required to be adjacent to $i$.

The company wants the total number of floors in the built skyscrapers to be as large as possible. Help it to choose the number of floors for each skyscraper in an optimal way, i.e. in such a way that all requirements are fulfilled, and among all such construction plans choose any plan with the maximum possible total number of floors.

这是一个更难的版本。在此版本中，$n \le 500\,000$。

贝尔兰首都的郊区正在积极建设。公司“内核恐慌”（Kernel Panic）负责在新贝尔尔斯克瓦（New Berlskva）建造一个摩天大楼住宅区。所有摩天大楼均沿高速公路建造。已知该公司已在高速公路上购买了 $n$ 块地块，并准备在每块地块上各建一座摩天大楼。

建筑师在规划摩天大楼时必须满足若干要求。首先，由于每块地块的土地性质不同，每座摩天大楼均有其最大允许楼层数限制。其次，根据该市的设计规范，不允许存在某座摩天大楼，其左右两侧（不一定相邻）均存在比它更高的摩天大楼。

形式化地，我们将地块编号为 $1$ 到 $n$。若第 $i$ 块地块上的摩天大楼有 $a_i$ 层，则必须满足 $a_i \le m_i$（即 $1 \le a_i \le m_i$）。此外，不能存在整数 $j$ 和 $k$，使得 $j \lt i \lt k$ 且 $a_j \gt a_i \lt a_k$。此处地块 $j$ 和 $k$ 不必与 $i$ 相邻。

该公司希望所建摩天大楼的总楼层数尽可能大。请帮助该公司为每座摩天大楼选定最优的楼层数，即：在满足所有约束条件的前提下，使总楼层数最大化；若有多种方案满足该最大总楼层数，任选其一即可。

The first line contains a single integer $n$ ($1 \leq n \leq 500\,000$) — the number of plots.

The second line contains the integers $m_1, m_2, \ldots, m_n$ ($1 \leq m_i \leq 10^9$) — the limit on the number of floors for every possible number of floors for a skyscraper on each plot.

第一行包含一个整数 $n$（$1 \leq n \leq 500\,000$）—— 表示地块的数量。

第二行包含整数 $m_1, m_2, \ldots, m_n$（$1 \leq m_i \leq 10^9$）—— 表示每块地块上建造摩天大楼时允许的最高楼层数。

Print $n$ integers $a_i$ — the number of floors in the plan for each skyscraper, such that all requirements are met, and the total number of floors in all skyscrapers is the maximum possible.

If there are multiple answers possible, print any of them.

输出 $n$ 个整数 $a_i$ —— 每座摩天大楼设计方案中的楼层数，使得所有要求均被满足，且所有摩天大楼的总楼层数达到最大可能值。

若存在多种可行答案，输出任意一种即可。

In the first example, you can build all skyscrapers with the highest possible height.

In the second test example, you cannot give the maximum height to all skyscrapers as this violates the design code restriction. The answer $[10, 6, 6]$ is optimal. Note that the answer of $[6, 6, 8]$ also satisfies all restrictions, but is not optimal.

在第一个例子中，你可以将所有摩天大楼都建造成可能的最高高度。

在第二个测试样例中，你无法将所有摩天大楼都赋予最大高度，因为这违反了设计规范的限制。答案 $[10, 6, 6]$ 是最优的。注意，答案 $[6, 6, 8]$ 同样满足所有限制条件，但并非最优。