eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Преобразование строковых функций:обратная задача

Преобразование строковых функций:обратная задача

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Для строки S определим Z-функцию следующим образом: Z[i] = lcp(S, S[i..|S|]), где lcp(S_1, S_2) равно длине наибольшего общего префикса строк S_1 и S_2. Например, для S = abacabaaZ-функция равна [8, 0, 1, 0, 3, 0, 1, 1].

Для строки S определим ее префикс-функцию: pi[i] = max{k | 0 k < i, S[1..k] = S[i - k + 1..i]}. Например, для S = abacabaa ее префикс-функция имеет вид: [0, 0, 1, 0, 1, 2, 3, 1].

Для некоторой строки S была посчитана ее префикс-функция, а строка S была утеряна. Ваша задача получить ее Z-функцию по заданной префикс-функции.

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

В первой строке входного файла содержится натуральное число N (1N200000), где N - длина S. Во второй строке записана префикс-функция строки S.

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

Выведите N чисел - искомую Z-функцию.

Пример

Входные данные #1
8
0 0 1 0 1 2 3 1
Выходные данные #1
8 0 1 0 3 0 1 1