题目描述

本题与 easy 唯一的区别是，不限制序列中的重复数字的出现。

瓜瓜在学字符串，他觉得喜欢字典序大的东西总是好的。某天他得到了一个长度为 $n$ 的序列 $\{a_i\}$，并希望增大它的字典序，但是他懒得思考，就把这个任务丢给了你。

你可以先把该序列划分成若干不相交的区间，然后翻转每个划分出的区间。

瓜瓜想知道，如何使用一次操作才能使结果的字典序尽可能大。

字典序：对于两个长为 $n$ 的序列 $\{a_i\}, \{b_i\}$，我们称 $\{a_i\}$ 的字典序比 $\{b_i\}$ 的字典序大，当且仅当存在 $1 \leqslant k \leqslant n$ 使得 $a_i = b_i$ 对 $i < k$ 成立，且 $a_k > b_k$。

输入描述

第一行有一个正整数 $n(1 \leqslant n \leqslant 10^5)$，表示序列的大小。

接下来有 $n$ 行，每行有一个正整数 $a_i$，其中 $1 \leqslant a_i \leqslant 10^5$。

输出描述

输出 $n$ 个数字, 表示翻转之后字典序最大的序列。

样例

5
2 3 2 3 1

3 2 3 2 1

5
2 3 1 2 3

3 2 3 2 1