Задачи
Преобразование строковых функций:обратная задача
Преобразование строковых функций:обратная задача
Для строки 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 (1 ≤ N ≤ 200000), где N - длина S. Во второй строке записана префикс-функция строки S.
Выходные данные
Выведите N чисел - искомую Z-функцию.
Пример
Входные данные #1
8 0 0 1 0 1 2 3 1
Выходные данные #1
8 0 1 0 3 0 1 1