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

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

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

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

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

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