Від префікс функції до z-функції

Автор справді хотів придумати легенду до цієї задачі, але колоквіум з матаналізу хотів автора більше.

Вам задана коректна префікс-функція деякого рядка. Обчисліть z-функцію цього ж рядка.

####Вхідні данні:

Перший рядок вхідного стандартного потоку містить число N (1 ≤ N ≤ 10^6). Наступний рядок містить N цілих невід'ємних чисел - опис префікс-функції.

####Вихідні данні:

Виведіть єдиний рядок з N цілих невід'ємних чисел - опис z-функції.

Приклади