Description

A binary search tree is a binary tree that has the following properties:

1. For any node, its key is greater than the keys stored in the left subtree.

2. For any node, its key is smaller than the keys stored in the right subtree.

3. For any node, the left subtree and the right subtree are binary search trees respectively as well.

4. Every node has a unique key. No two nodes share the same key.

Reference: Build a Binary Search Tree from a postorder sequence

For example, the two following trees are binary search trees.

Now, given a postorder of a binary search tree, please output the preorder of it.

The graph of the sample input is as follow.

Input

The input contains only one line represent the postorder of the binary tree. The value are pairwise distinct.
a₁ a₂ a₃ ...... a_N
(1 <= N <= 200000, -1000000000 <= a_i <= 1000000000)

Output

Please output the preorder of the binary search tree according to the input.
Guarantee that there's only one answer since we can prove that no two different binary tree have the same postorder and inorder.
Remember to output newline character at the end of the line.
Don't output additional space at the end.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss