CF675D Tree Construction
题目描述
在编程课上，Vasya 遇到了一道难题。然而，他不知道如何解题，也没法在网上找到解法，所以他向你求助这道题。
给定一个序列 $a$，序列包含 $n$ 个互不相同的整数，用于构建二叉搜索树。以下为构建流程：
1. $a_1$ 为树的根节点。
2. $a_2,a_3,\cdots,a_n$ 被依次添加。$a_i$ 元素被添加时，需要从根节点开始穿过树，并遵循下列规则：
1. 指向当前节点的指针作为根。
2. 如果 $a_i$ 比当前节点的值大，当前节点更新为右儿子；反之，当前节点更新为左儿子。
3. 如果当前节点不存在所需的儿子，即创建新的节点，其值为 $a_i$。
输入格式
第一行一个整数 $n$ ($2\le n\le 10^5$)，表示序列 $a$ 的长度。
第二行 $n$ 个互不相同的整数 $a_i$ ($1\le a_i\le 10^9$)，表示序列 $a$。
输出格式
一行 $n-1$ 个整数，表示 $a_2,a_3,\cdots a_n$ 在树中父亲节点的值。
说明/提示
下图代表样例一的二叉搜索树。
下图表示样例二的二叉搜索树。
