From the prefix function to the z-function

The author intended to create a legend for this problem, but the calculus colloquium demanded more of their attention.

You are provided with the correct prefix function of a specific string. Your task is to compute the z-function for this same string.

Input

The first line of the input contains the integer N (1 ≤ N ≤ 10^6). The following line contains N non-negative integers, which represent the prefix function.

Output

Output a single line containing N non-negative integers, which represent the z-function.

Examples