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 | 0k < 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