BST Inorder Traversal

Source: Phuoc Hung OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Build a binary search tree (BST) from $a_1,a_2,\ldots,a_n$ in the given insertion order. A smaller key goes to the left child, a larger key goes to the right child, and duplicate keys are ignored.

After the tree is built, perform an inorder traversal. For each node, inorder first traverses the entire left subtree, then visits the current node, then traverses the entire right subtree.

Print the keys in exactly that visitation order.

Input

The first line contains $n$.

If $n>0$, the next line contains $n$ signed integers $a_1,a_2,\ldots,a_n$. If $n=0$, this line is absent.

Output

If the tree is non-empty, print the inorder keys on one line separated by one space.

If the tree is empty, print EMPTY.

Subtasks

Subtask 1 (20 points): $0\le n\le 20$.

Subtask 2 (30 points): $0\le n\le 5000$.

Subtask 3 (50 points): $0\le n\le 200000$.

In all subtasks, $-2^{63}\le a_i\le 2^{63}-1$. Duplicate keys are ignored.

Examples

Input

7
8 3 10 1 6 14 4

Output

1 3 4 6 8 10 14

Explanation

The tree is built from the insertion order in the input. Its inorder traversal visits keys $1,3,4,6,8,10,14$ in that order, producing the shown output.