CF1313C2 Skyscrapers (hard version)

这题是 [CF1313C1](https://www.luogu.com.cn/problem/CF1313C1) 的较难版本。这个版本中 $1 \leq n \leq 500000$。 Berland要起摩天大厦了。所有的摩天大厦都在高速公路附近建。发展商买了 $n$ 块地准备建 $n$ 栋摩天大厦，一块地一栋。 当规划一间摩天大厦的时候，建筑师要考虑一些条件。 第一，因为每栋摩天大厦有不同的用途，所以每栋摩天大厦都有自己的层数限制，也就是说，这栋摩天大厦的高度不能超过给定的值 $m_i$。 第二，根据城市的建设规则，一栋摩天大厦不能同时在左右有比它高的摩天大厦。 如果规范地表示，让我们把地编上一个编号从 $1$ 到 $n$。那么如果在第 $i$ 块地的摩天大厦有 $a_i$ 层，那么我们需要保证 $1 \le a_i \le m_i$。另外，这里不可以有整数 $j$ 和 $k$ 满足 $j < i < k$ 并且 $a_j > a_i < a_k$。第 $j, k$ 块地并不需要与第 $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.