Skyscrapers (hard version)
Contest: Codeforces Round 622 (Div. 2)
Difficulty rating: 1900
Tags: data structures, dp, greedy

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 < i < k$$$ and $$$a_j > a_i < 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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
5
1 2 3 2 1

Example output:
1 2 3 2 1

Example input:
3
10 6 8

Example output:
10 6 6

Editorial:
Let's solve the task on an array $$$m$$$ of length $$$n$$$. Let's find a minimal element in this array. Let it be on the $$$i$$$-th ($$$1 \leq i \leq n$$$) position. We can build the skyscraper at the $$$i$$$-th position as high as possible, that is $$$a_i = m_i$$$.
Now we should make a choice — we need to equate to $$$a_i$$$ either the left part of the array ($$$a_1 = a_i, a_2 = a_i, \ldots, a_{i-1} = a_i$$$), or the right part ($$$a_{i+1} = a_i, a_{i+2} = a_i, \ldots, a_{n} = a_i$$$), and solve the task recursively on the remaining part of the array, until we get an array of length 1.
The described recursive task has $$$n$$$ different states. Depending on the approach of finding a minimal element on a segment, we can get solutions of complexity $$$O(n^2)$$$, $$$O(n \sqrt{n})$$$ or $$$O(n \log n)$$$.
There is another solution. It can be proved that the answer looks like this: from the start of the array the heights are non-decreasing, and starting from the certain skyscraper the heights are non-increasing. Let's call a skyscraper "peak" if there is the change of direction on this skyscraper. We are to find the optimal "peak".
We can build arrays $$$l$$$ and $$$r$$$ of length $$$n$$$. Let's iterate positions from left to right. Let we are on the $$$i$$$-th position. If $$$m_i$$$ is the smallest element among $$$m_1, \ldots, m_i$$$, then $$$l_i = i \times m_i$$$. Otherwise, let's look at $$$m_1, m_2, \ldots, m_{i-1}$$$ and take the rightest number smaller than $$$m_i$$$, let it be $$$m_j$$$ on the $$$j$$$-th position. Then $$$l_i = l_j + (i - j) \times m_i$$$. Similarly, we build $$$r$$$ (but changing the direction from right to left). The "peak" is the skyscraper $$$t$$$ such that $$$l_t + r_t - m_t$$$ is maximal.
The complexity of this solution can be $$$O(n^2)$$$, $$$O(n \log n)$$$, $$$O(n)$$$ depending on the approach of finding "nearest" numbers to the right and to the left that are smaller than the current one.