Перетворення рядкових функцій: обернена задача
Перетворення рядкових функцій: обернена задача
Для рядка 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
-функцію.
Приклад
8 0 0 1 0 1 2 3 1
8 0 1 0 3 0 1 1