C. 二叉搜索树最优生成序列

题目描述

众所周知，二叉搜索树的形状与我们插入的键的顺序密切相关。确切地说：

1. 将键 $k$ 插入一棵空树，然后将树变成只有一个节点；
2. 将键 $k$ 插入非空树，如果 $k$ 小于根，则将其插入左侧子树；否则将 $k$ 插入右侧子树。

我们将键的顺序称为“一棵树的顺序”，您的任务是，给定一棵树的键的顺序，找到字典顺序最小的一棵树的顺序，该顺序生成同一棵树。如果两棵树相同，数值一样并且只有它们具有相同的形状。

输入格式

第一行输入一个正整数 $n$ 第二行输入 $n$ 个不同的正整数，表示键

输出格式

输出 $n$ 个数，表示答案

样例

输入

4
1 3 4 2

输出

1 3 2 4

数据范围与提示

• $100\%$ 的数据：$n \le 100000$
• 数据随机生成