在编程课上,Vasya 被布置了一个难题。然而,他不会编码,也无法在互联网上找到解决方案,所以他请求你帮忙。
给定一个序列 $$$a$$$,由 $$$n$$$ 不同的整数组成,用于构造二叉搜索树。下面是构建过程的正式描述。
1. 第一个元素 $$$a_1$$$ 成为树的根。
2. 元素$$$a_2, a_3, \ldots, a_n$$$ 一一相加。要添加元素 $$$a_i$$$ 需要从根开始遍历树并使用以下规则: 指向当前节点的指针设置为根。 如果 $$$a_i$$$ 大于当前节点中的值,则其右子节点成为当前节点。否则,当前节点的左子节点将成为新的当前节点。 如果在某个时刻没有所需的子节点,则会创建新节点,并为其分配值 $$$a_i$$$ 并成为当前节点的相应子节点。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100\,000$$$) — 序列 $$$a$$$ 的长度。
第二行包含 $$$n$$$ 不同的整数 $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) - 序列 $$$a$$$ 本身。
输出
输出 $$$n - 1$$$ 整数。对于所有 $$$i > 1$$$ 打印写入节点中的值,该节点是值为 $$$a_i$$$ 的节点的父节点。
示例
输入 #1
3 1 2 3
输出 #1
1 2
输入 #2
5 4 2 3 1 6
输出 #2
4 2 2 4