TopCoder

Thumb qz2vnqoblj6vp6q
miku
https://chino.taipei

User's AC Ratio

67.5% (27/40)

Submission's AC Ratio

25.5% (55/216)

Tags

Description

「我是你爸爸」   Star Wars,Darth Vader。

「為什麼你要代替你爹」   《天龍八部》, 蕭峰。

「你名義老爸在你後面,他很火」   至尊三十六計之偷天換日, 電腦

給你N個數1~N,依照所給的順序插入,建成一棵二元搜尋樹, 問每一個數的父節點是誰?

--你可以決定你的命運,但你無法決定你的老爸是誰--

                     一顆二元樹節點的自白。

Input Format

輸入第一行有一個正整數N(N<1000001)

接下來有N行,每行一個數,為依序插入的數字。

Output Format

輸出N行,第i行為數字i的父節點。

如果沒有父節點,輸出0。

Sample Input

5
3
1
2
4
5

Sample Output

3
1
0
3
4

Hints

Problem Source

原TIOJ1332 / problem setter:seanwu

Subtasks

For Testdata: 0 ~ 0, Score: 25
For Testdata: 1 ~ 1, Score: 25
For Testdata: 2 ~ 2, Score: 25
For Testdata: 3 ~ 3, Score: 25
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 8000 65536 65536
1 8000 65536 65536
2 8000 65536 65536
3 8000 65536 65536