Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Tree Construction

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputDuring the programming classes Vasya was assigned a difficult problem. However, he doesn't know how to code and was unable to find the solution in the Internet, so he asks you to help.

You are given a sequence $$$a$$$, consisting of $$$n$$$ distinct integers, that is used to construct the binary search tree. Below is the formal description of the construction process.

- First element $$$a_1$$$ becomes the root of the tree.
- Elements $$$a_2, a_3, \ldots, a_n$$$ are added one by one. To add element $$$a_i$$$ one needs to traverse the tree starting from the root and using the following rules:
- The pointer to the current node is set to the root.
- If $$$a_i$$$ is greater than the value in the current node, then its right child becomes the current node. Otherwise, the left child of the current node becomes the new current node.
- If at some point there is no required child, the new node is created, it is assigned value $$$a_i$$$ and becomes the corresponding child of the current node.

Input

The first line of the input contains a single integer $$$n$$$ ($$$2 \leq n \leq 100\,000$$$) — the length of the sequence $$$a$$$.

The second line contains $$$n$$$ distinct integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — the sequence $$$a$$$ itself.

Output

Output $$$n - 1$$$ integers. For all $$$i > 1$$$ print the value written in the node that is the parent of the node with value $$$a_i$$$ in it.

Examples

Input

3

1 2 3

Output

1 2

Input

5

4 2 3 1 6

Output

4 2 2 4

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/21/2021 03:14:55 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|