Codeforces Round #353 (Div. 2) D. Tree Construction （构造二叉搜索树）

Codeforces Round #353 (Div. 2) D. Tree Construction （构造二叉搜索树）

D. Tree Construction

time limit per test

memory limit per test

input

output

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

First elementa1Elementsa2,a3, ...,anare added one by one. To add elementai

The pointer to the current node is set to the root.IfaiIf at some point there is no required child, the new node is created, it is assigned valueai

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the length of the sequence a.

The second line contains n distinct integers ai (1 ≤ ai ≤ 109) — the sequence a

Output

Output n - 1 integers. For all i > 1 print the value written in the node that is the parent of the node with value ai

Examples

input

31 2 3

output

1 2

input

54 2 3 1 6

output

4 2 2 4

Note

Picture below represents the tree obtained in the first sample.

Picture below represents the tree obtained in the second sample.

题解：

给你一堆结点，按照题目规则叫你构造一棵二叉搜索树，并且按输入顺序输出除根节点以外的所有节点的父亲。

n有100000，如果直接建树可能会TLE。因为这是一棵二叉搜索树。所以我们可以利用二叉搜索树的性质。

因为对于当前输入的结点V，找到已经输入的最大的Left和最小的Right，其中Left< V < Right。其中，Left和Right必定是祖先和后代的关系，（不可能有公共祖先的）。对于当前的输入的结点V必定是Left的左子树，或者Right的右子树。这两个位置一定有一个位置是当前结点V的。

AC代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。