List BST Leaves in Descending Order

Source: Phuoc Hung OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Build a BST from $a_1,a_2,\ldots,a_n$ in insertion order. Duplicate keys are ignored.

A node is a leaf if it has neither a left child nor a right child. In a one-node tree, the root itself is a leaf.

Collect the keys of all leaf nodes and print them in strictly descending 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 has at least one leaf, print all leaf keys in descending order 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 insertion keys are ignored.

Examples

Input

7
8 3 10 1 6 14 4

Output

14 4 1

Explanation

In the constructed tree, the nodes with keys $1$, $4$, and $14$ have neither a left child nor a right child, so these are exactly the leaf nodes. Every other node has at least one child.

The leaf keys are $1,4,14$. In descending order they are $14,4,1$, so the program prints 14 4 1.