E. Extra Character
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a string $$$s$$$ of length $$$n$$$, the Z-function of $$$s$$$ is a sequence of $$$n$$$ integers such that the $$$i$$$-th element is equal to the largest nonnegative integer $$$x$$$ no greater than $$$n$$$ such that $$$s_j=s_{i+j-1}$$$ for all $$$1 \le j \le x$$$. For example, the $$$i$$$-th element is $$$0$$$ if $$$s_i \neq s_1$$$, and the first element is always $$$n$$$.

Your friend recently sent you a string $$$s$$$ of length $$$n$$$. He needs to compute the Z-function of this string but does not have enough time to compute it himself. You quickly compute it for him and send it back to your friend.

However, it seems like your friend made a mistake; he made a typo, and it turned out that the string he sent you had an extra character in the front. Unfortunately, neither you nor your friend kept a copy of the original string. Still, you want to know the Z-function of the intended string.

Please find the Z-function of the intended string $$$t=s_{2\ldots n}$$$. For each position, output $$$-1$$$ instead if the value on the specific position cannot be uniquely determined.

Input

The first line contains a single integer $$$n$$$, the length of the original string. ($$$2 \leq n \leq 10^6$$$)

The second line contains $$$n$$$ integers $$$p_1, p_2, \cdots, p_n$$$, the Z-function of the original string. ($$$0 \leq p_i \leq n$$$)

It is guaranteed that a string corresponding to the given Z-function exists.

Output

Output $$$n - 1$$$ integers $$$q_1, q_2, \cdots, q_{n-1}$$$, the Z-function of the intended string $$$s_{2\ldots n}$$$.

If the value cannot be uniquely determined for some position, output $$$-1$$$ for the position.

Examples
Input
5
5 4 3 2 1
Output
4 3 2 1
Input
7
7 2 1 0 2 1 0
Output
6 1 0 -1 1 0
Input
7
7 0 1 0 3 0 1
Output
6 0 0 0 2 0