eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

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

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

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

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

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

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

Examples

Input example #1
10
0 1 0 1 0 1 0 1 2 3
Output example #1
0 1 0 1 0 1 0 3 1 0