[TJOI2011] 树的序

题目描述

众所周知，二叉查找树的形态和键值的插入顺序密切相关。准确的讲： $1$ 、空树中加入一个键值 $k$ ，则变为只有一个结点的二叉查找树，此结点的键值即为 $k$ ； $2$ 、在非空树中插入一个键值 $k$ ，若 $k$ 小于其根的键值，则在其左子树中插入 $k$ ，否则在其右子树中插入 $k$ 。

我们将一棵二叉查找树的键值插入序列称为树的生成序列，现给出一个生成序列，求与其生成同样二叉查找树的所有生成序列中字典序最小的那个，其中，字典序关系是指对两个长度同为 $n$ 的生成序列，先比较第一个插入键值，再比较第二个，依此类推。

输入格式

第一行，一个整数， $n$ ，表示二叉查找树的结点个数。第二行，有 $n$ 个正整数， $k_1$ 到 $k_n$ ，表示生成序列，简单起见， $k_1$ ~ $k_n$ 为一个 $1$ 到 $n$ 的排列。

输出格式

一行， $n$ 个正整数，为能够生成同样二叉查找数的所有生成序列中最小的。

样例 #1

样例输入 #1

4
1 3 4 2

样例输出 #1

1 3 2 4

提示

对于 $20\%$ 的数据，$n ≤ 10$ 。

对于 $50\%$ 的数据， $n ≤ 100$ 。

对于 $100\%$ 的数据， $n ≤ 100,000$ 。