#P1377. [TJOI2011] 树的序

[TJOI2011] 树的序

题目描述

众所周知,二叉查找树的形态和键值的插入顺序密切相关。准确的讲:

  1. 空树中加入一个键值 kk,则变为只有一个结点的二叉查找树,此结点的键值即为 kk
  2. 在非空树中插入一个键值 kk,若 kk 小于其根的键值,则在其左子树中插入 kk,否则在其右子树中插入 kk

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

输入格式

第一行,一个整数 nn,表示二叉查找树的结点个数。第二行,有 nn 个正整数 k1,k2,,knk_1, k_2, \cdots,k_n,表示生成序列,简单起见,k1knk_1 \sim k_n 为一个 11nn 的排列。

输出格式

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

4
1 3 4 2

1 3 2 4

提示

数据范围及约定

  • 对于 20%20\% 的数据, 1n101\le n ≤ 10
  • 对于 50%50\% 的数据, 1n1001\le n ≤ 100
  • 对于 100%100\% 的数据, 1n1051\le n ≤ 10^5