题目描述

这题是 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$ 块地相邻。

发展商想要使得每块地上摩天大厦的楼层数之和最大。也请帮他找出在任意一个最优状况中每个摩天大厦的高度。也就是，要让建筑师考虑的条件都符合，而且要使得每块地上摩天大厦的楼层数之和最大。

输入格式

第一行有一个整数 $n$ $(1 \leq n \leq 500000)$，表示发展商购买了 $n$ 块地。

第二行，$n$ 个整数 $m_1, m_2, \ldots, m_n$ $(1 \leq m_i \leq 10^9)$，表示每块地上建摩天大厦层数的限制。

输出格式

输出 $n$ 个整数 $a_i$，表示在最优状况中每个摩天大厦的高度，而且要符合建筑师考虑的条件。如果答案有多种，你可以输出任何一种。

输入输出样例 #1

输入 #1

5
1 2 3 2 1

输出 #1

1 2 3 2 1

输入输出样例 #2

输入 #2

3
10 6 8

输出 #2

10 6 6