P1377 [TJOI2011] Tree Order

It is well known that the shape of a binary search tree (BST) is closely related to the insertion order of keys. Specifically: 1. Inserting a key $k$ into an empty tree yields a BST with a single node whose key is $k$. 2. When inserting a key $k$ into a non-empty tree, if $k$ is less than the key of its root, insert $k$ into its left subtree; otherwise, insert it into its right subtree. We call an insertion sequence of keys for a BST a generating sequence of the tree. Given one generating sequence, find the lexicographically smallest generating sequence among all sequences that generate the same BST. Here, the lexicographic order means that for two generating sequences both of length $n$, we first compare the first inserted keys, then the second, and so on.

The first line contains an integer $n$, the number of nodes in the BST. The second line contains $n$ positive integers $k_1, k_2, \cdots, k_n$, representing the generating sequence. For simplicity, $k_1 \sim k_n$ is a permutation of $1$ to $n$.

One line with $n$ positive integers, which is the lexicographically smallest among all generating sequences that can generate the same BST.

Constraints and Conventions - For $20\%$ of the testdata, $1 \le n \le 10$. - For $50\%$ of the testdata, $1 \le n \le 100$. - For $100\%$ of the testdata, $1 \le n \le 10^5$. Translated by ChatGPT 5