% Origin: 20100422, SPbSU, Spring 2010, Group A, Fourth Training - Strings
% Author: Ivan Kazmenko
% Text Author: Ivan Kazmenko
% Tests Author: Ivan Kazmenko

\begin{problem}{От префикс-функции к z-функции}
{\textsl{стандартный ввод}}{\textsl{стандартный вывод}}
%{ptoz.in}{ptoz.out}
{2 секунды}{256 мебибайт}{}

\textit{Префикс-функция} $p (i)$ для строки $s = s_1 s_2 \ldots s_n$
определяется от позиции $i$ ($1 \le i \le n$) в строке так:
$p (i)$ "--- это максимальная длина собственного префикса строки
$s_1 s_2 \ldots s_i$, равного её собственному суффиксу.
Напомним, что \textit{собственный префикс} строки $s = s_1 s_2 \ldots s_n$
"--- это строка $s_1 s_2 \ldots s_r$ для некоторого $r < n$.
Аналогично, \textit{собственный суффикс} строки $s = s_1 s_2 \ldots s_n$
"--- это строка $s_l s_2 \ldots s_n$ для некоторого $l > 1$.
%В этой задаче считается, что $p (1) = 0$.

\textit{Z-функция} $z (i)$ для строки $s = s_1 s_2 \ldots s_n$
определяется от позиции $i$ ($1 \le i \le n$) в строке так:
$z (1) = 0$, а для $i > 1$ $z (i)$ "--- это максимальное число такое,
что строки $s_1 s_2 \ldots s_{z (i)}$
и $s_i s_{i + 1} \ldots s_{i + z (i) - 1}$ совпадают.

Даны длина строки $n$ и значения префикс-функции
$p (1)$, $p (2)$, $\ldots$, $p (n)$ для этой строки.
Найдите для этой строки значения z-функции
$z (1)$, $z (2)$, $\ldots$, $z (n)$.

\InputFile

В первой строчке входного файла задано целое число $n$
($1 \le n \le 1\,000\,000$).
Во второй строчке заданы $n$ чисел через пробел "--- значения префикс-функции
$p (1)$, $p (2)$, $\ldots$, $p (n)$.
Гарантируется, что существует строка длины $n$, состоящая
из строчных букв латинского алфавита, для которой префикс-функция
от позиций $1$, $2$, $\ldots$, $n$ принимает данные значения.

\OutputFile

В первой строчке выходного файла выведите $n$ чисел через пробел "---
значения z-функции для строки, имеющей данную префикс-функцию.

\Examples

\begin{example}
\exmp{
6
0 0 1 2 3 4
}{
0 0 4 0 2 0
}%
\exmp{
7
0 0 0 1 2 3 4
}{
0 0 0 4 0 0 1
}%
\exmp{
4
0 0 0 0
}{
0 0 0 0
}%
\end{example}

\end{problem}
