Z-функция по префикс-функции

1000 мс · 256 МБ · всё или ничего

Дана префикс-функция некоторой строки. Восстановите её Z-функцию - не восстанавливая саму строку.

В первой строке - длина $n$ ( $1 \le n \le 10^6$ ).

Во второй строке - $n$ значений префикс-функции некоторой строки из строчных латинских букв.

Выведите $n$ значений Z-функции той же строки. Первое из них равно $n$ .

ввод

7
0 0 1 0 1 2 3

вывод

7 0 1 0 3 0 1

ввод

5
0 1 2 3 4

вывод

5 4 3 2 1

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.