Lexicographically Smallest Generation Sequence in a Binary Search Tree

A binary search tree (BST) is built by inserting keys in a given order. The insertion rules are as follows:

• If the tree is empty and you insert a key \(k\), the tree becomes a single node with key \(k\).
• If the tree is non-empty and you insert a key \(k\), then if \(k\) is less than the root's key, \(k\) is inserted into the left subtree; otherwise, it is inserted into the right subtree.

Any permutation of keys that, when inserted in this way, produces the same BST is called a generation sequence of the tree.

Given a generation sequence used to construct a BST, your task is to find the lexicographically smallest generation sequence among all sequences that generate the same BST. Here, lexicographical order is defined as follows: for any two sequences of the same length \(n\), compare the first key of each sequence; if they are the same, compare the second key; and so on.

Hint: Note that every valid generation sequence must start with the root of the tree. Moreover, if you recursively compute the lexicographically smallest generation sequence for the left and right subtrees, the answer is the root followed by the lexicographically smallest merge of the two sequences. For merging two sequences, use a greedy approach: at each step, choose the smaller front element from the two sequences.

inputFormat

The first line contains an integer \(n\) \( (1 \le n \le 10^5)\) representing the number of keys. The second line contains \(n\) space-separated integers representing the generation sequence used to construct the BST.

outputFormat

Output a single line containing the lexicographically smallest generation sequence (space-separated) that produces the same BST.

sample

3
2 1 3

2 1 3