Tree Construction

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

A sequence of distinct integers $a_1,a_2,\ldots,a_n$ is used to construct a binary search tree in the following order.

Key $a_1$ becomes the root.

For every $i$ from $2$ to $n$, start at the root. If $a_i$ is smaller than the current key, move to the left child; if it is larger, move to the right child. When the required child is empty, create a new node with key $a_i$ there and finish this insertion.

For every inserted element from the second one onward, determine the key stored in the direct parent of the newly created node.

Input

The first line contains $n$.

The second line contains $n$ distinct integers $a_1,a_2,\ldots,a_n$ in insertion order.

Output

Print $n-1$ integers on one line. For every $2\le i\le n$, the $(i-1)$-th output integer is the key stored in the parent of the node with key $a_i$.

Separate consecutive integers by one space.

Subtasks

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

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

Subtask 3 (50 points): $2\le n\le 100000$, $1\le a_i\le 10^9$.

In all subtasks, all $a_i$ are distinct.

Examples

Input

5
4 2 3 1 6

Output

4 2 2 4

Explanation

Key $4$ is the root. Inserting $2$ makes it the left child of $4$, so its parent is $4$.

Next, $3$ goes left from $4$ to $2$ and becomes the right child of $2$, so its parent is $2$. Key $1$ becomes the left child of $2$, and key $6$ becomes the right child of $4$.

Therefore the parent keys for $a_2,a_3,a_4,a_5$ are 4 2 2 4.