e-olymp
Competitions

Spanning Tree + DSU

Ancestors

Examining the genes of several thousand people, scientists assumed that all mankind originated from a small tribe of20people who lived somewhere in West Africa.

United Association of Cloned Martians decided to conduct similar studies for the inhabitants of Mars. Write a program to ACM, which, using the results of a large genetic study of Martians, assigning him the progenitor of a Martian.

Input

The first line contains the number n (1 < n 100000) of surveyed Martians. Is followed bynlines, each containing a single integer from 0 to n. In the (i+1)-th line the number is the parent of i-th Martian, or0, if it has no parent (i.e. he is the father, like Adam and Eve in the Bible). The input data does not contain cycles.

Output

Print for each Martian his ancestor, or 0 if he is the father.

Time limit 1 second
Memory limit 64 MiB
Input example #1
7
3
3
6
7
4
0
0
Output example #1
6
6
6
7
7
0
0