33745번 - Extra Character 다국어

문제

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.

입력

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 $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.

제한

힌트