CF675D.Tree Construction

During 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.

1. First element $a_1$ becomes the root of the tree.
2. 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:
   1. The pointer to the current node is set to the root.
   2. 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.
   3. 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.

在编程课上，瓦西娅被布置了一道难题。然而，他不会编程，也无法在网上找到解决方案，因此他请求你帮忙。

给你一个由 $n$ 个互不相同的整数组成的序列 $a$，该序列用于构建一棵二叉搜索树。以下是该构建过程的形式化描述：

1. 第一个元素 $a_1$ 成为树的根节点。
2. 元素 $a_2, a_3, \ldots, a_n$ 依次插入树中。插入元素 $a_i$ 时，需从根节点开始遍历树，并遵循以下规则：
   1. 将当前节点指针设为根节点。
   2. 若 $a_i$ 的值大于当前节点的值，则将当前节点的右子节点设为新的当前节点；否则，将当前节点的左子节点设为新的当前节点。
   3. 若在某一步中，所需子节点（左或右）不存在，则创建一个新节点，将其赋值为 $a_i$，并作为当前节点的对应子节点。

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.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 100\,000$）——序列 $a$ 的长度。

第二行包含 $n$ 个互不相同的整数 $a_i$（$1 \leq a_i \leq 10^9$）——序列 $a$ 本身。

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

输出 $n - 1$ 个整数。对于所有 $i > 1$，输出值为 $a_i$ 的节点在树中的父节点所存储的值。