От префикс-функции до z-функции

Автор действительно хотел придумать легенду к этой задаче, но коллоквиум по матанализу оказался важнее.

Вам дана корректная префикс-функция некоторой строки. Ваша задача — вычислить z-функцию для этой же строки.

Входные данные

Первая строка входных данных содержит число N (1 ≤ N ≤ 10^6). Во второй строке приведены N целых неотрицательных чисел, представляющих собой описание префикс-функции.

Выходные данные

Выведите в одну строку N целых неотрицательных чисел, которые составляют описание z-функции.

Примеры