F. 建树

题目描述

在编程课上，Vasya 遇到了一道难题。给定一个序列 $a$，序列包含 $n$ 个互不相同的整数，用于构建二叉搜索树，构建流程如下：

1. $a_1$ 为树的根节点；
2. $a_2, a_3, \dots, a_n$ 被依次添加。添加 $a_i$ 时，需要从根节点开始穿过树，并遵循下列规则：
   • 指向当前节点的指针作为根；
   • 如果 $a_i$ 比当前节点的值大，则当前节点更新为右儿子；反之，当前节点更新为左儿子；
   • 如果当前节点不存在所需的儿子，则创建新的节点，其值为 $a_i$。

请输出 $a_2, a_3, \dots, a_n$ 在树中父亲节点的值。

输入格式

第一行一个整数 $n\ (2 \le n < 10^5)$，表示序列 $a$ 的长度。 第二行 $n$ 个互不相同的整数 $a_i\ (1 \le a_i \le 10^9)$，表示序列 $a$。

输出格式

一行 $n-1$ 个整数，表示 $a_2, a_3, \dots, a_n$ 在树中父亲节点的值。

样例

输入样例 #1

3
1 2 3

输出样例 #1

1 2

输入样例 #2

5
4 2 3 1 6

输出样例 #2

4 2 2 4

数据范围与提示

• $2 \le n < 10^5$
• $1 \le a_i \le 10^9$
• 序列中所有整数互不相同