BST Inorder Traversal from Preorder Sequence

Given the preorder traversal of a binary search tree (BST), your task is to construct the BST and then output its inorder traversal. Recall that in a BST, for every node, all nodes in its left subtree have keys that are less than the node's key, and all nodes in its right subtree have keys that are greater. The BST can be uniquely constructed from its preorder traversal.

The construction algorithm uses the fact that the first element in the preorder sequence is the root. Subsequently, elements less than the root belong to the left subtree and the remaining elements form the right subtree. This process can be implemented recursively with an upper bound constraint.

Formally, let (preorder) be the given list of numbers. We construct the BST using a recursive function as follows: [ \text{buildBST}(preorder,; index,; bound) = \begin{cases} \text{NULL}, & \text{if } index = |preorder| \text{ or } preorder[index] > bound \ \text{Node}(preorder[index]), & \text{otherwise} \end{cases} ] where (index) is a pointer to the current element in the preorder list, and (bound) is the upper limit for the node values in the current subtree.

After constructing the BST, performing an inorder traversal (left-root-right) will yield the sorted order of the input values. Your output should be the inorder traversal of the constructed BST.

inputFormat

The input consists of two lines. The first line contains a single integer (n) ( (1 \leq n \leq 10^5) ) which represents the number of nodes in the BST. The second line contains (n) space-separated integers representing the preorder traversal of the BST.

outputFormat

Output a single line containing the inorder traversal of the constructed BST. The integers must be space-separated.## sample

5
8 5 1 7 10

1 5 7 8 10