← 返回题目列表

Codeforces · 675/D

D. 树结构

中文机器翻译题面 查看原题

在编程课上,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