题目描述

二叉查找树的形态与键值的插入顺序密切相关，具体规则如下：

1. 若当前树为空，插入一个键值 $k$ 后，树变为只有一个结点的二叉查找树，该结点的键值为 $k$。
2. 若当前树非空，插入一个键值 $k$，若 $k$ 小于根结点的键值，则在左子树中递归插入 $k$；否则在右子树中递归插入 $k$。

给定一个由 $n$ 个互不相同的正整数构成的插入序列，求所有能生成同一棵二叉查找树的插入序列中，字典序最小的那一个。字典序的比较规则为：从第一个元素开始逐位比较，较小的序列字典序更小。

输入格式

第一行，一个整数 $n$，表示二叉查找树的结点个数。

第二行，$n$ 个正整数 $k_1, k_2, \cdots, k_n$，表示给定的插入序列，其中 $k_1 \sim k_n$ 是 $1$ 到 $n$ 的一个排列。

输出格式

一行，$n$ 个正整数，用空格隔开，表示字典序最小的等价插入序列。

样例

4
1 3 4 2

1 3 2 4

提示

数据范围及约定

• 对于 $20\%$ 的数据，$1 \leq n \leq 10$。
• 对于 $50\%$ 的数据，$1 \leq n \leq 100$。
• 对于 $100\%$ 的数据，$1 \leq n \leq 10^5$。