题目描述

我们曾经做过“二叉树的顺序储存结构”这一题，你有没有想过，当树全部偏向一侧，那么树的高度将会很高，这样的树是不完美的，是很丑陋的，那么，我们应该如何编排呢，今天就让我来tell you！ 众所周知，二叉搜索树的形状与我们插入的键的顺序有很大的关系。准确地说： 1。向空树插入键k，然后树将变为具有只有一个节点； 2。将键k插入非空树，如果k小于根，则插入 它位于左子树，否则将k插入右子树。 我们把插入的键的顺序称为“树的顺序”，你的任务是，给定一个树的顺序，找到另一个树的顺序（尽可能的做出最多升序的子序列 ，例如：1 3 4 2，其中2,4是可以互换的,且互换后多了子序列 {2,4},所以答案是1 3 2 4)，生成相同的一棵树。两棵树只有在形状相同的情况下才是相同的。

输入格式

输入文件中有多个测试用例。每个测试用例的第一行是一个整数n（n <= 100,000），表示节点数。第二行有n个整数，k1到kn，表示树的顺序。如果更简单，k1到kn是1到n的序列。

输出格式

一行有n个整数，它是树的顺序，它生成具有最少字典的相同树。

4
1 3 4 2

1 3 2 4

提示

Little snail