Minimum and Maximum in a BST

Source: Phuoc Hung OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Start with an empty BST. Insert $a_1,a_2,\ldots,a_n$ in the given order: smaller keys go left, larger keys go right, and a new node is created at the first empty child position. If a key already exists, ignore that duplicate insertion.

After the tree is built, determine the smallest and the largest key currently stored in the BST.

Input

The first line contains $n$.

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

Output

If the tree is empty, print EMPTY.

Otherwise print two integers on one line: the minimum key followed by the maximum key.

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, every $a_i$ is a signed 64-bit integer. Duplicate keys are ignored.

Examples

Input

7
8 3 10 1 6 14 4

Output

1 14

Explanation

After all insertions, the stored keys are $\{1,3,4,6,8,10,14\}$. The minimum is $1$ and the maximum is $14$, so the program prints 1 14.