4261. [TJOI2011] 树的序

【题目背景】

二叉查找树（Binary Search Tree）是一种非常基础且重要的数据结构。本题探讨的是二叉查找树的形态与元素插入顺序之间的逻辑关系。

【题目描述】

众所周知，二叉查找树的形态和键值的插入顺序密切相关。准确的讲：
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

【样例说明】

输入的序列 1 3 4 2 生成的二叉查找树形态如下：
1 是根，3 是 1 的右儿子，4 是 3 的右儿子，2 是 3 的左儿子。
该树的先序遍历序列为 1 3 2 4，这也是字典序最小的生成序列。

【数据规模与约定】

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

【来源】

TJOI2011 / 洛谷 P1377