Перетворення рядкових функцій: обернена задача#4907
Для рядка визначимо -функцію наступним чином: Z[i] = lcp(S, S[i..|S|]), де lcp(S_1, S_2) дорівнює довжині найбільшого спільного префікса рядків S_1 та S_2. Наприклад, для S = abacabaa -функція дорівнює [8, 0, 1, 0, 3, 0, 1, 1].
Для рядка визначимо його префікс-функцію: pi[i] = \max\{k \mid 0 \le k < i, S[1..k] = S[i - k + 1..i]\}. Наприклад, для S = abacabaa його префікс-функція має вигляд: [0, 0, 1, 0, 1, 2, 3, 1].
Для деякого рядка була побудована його префікс-функція, а рядок було втрачено. Ваша задача отримати його -функцію за заданою префікс-функцією.
У першому рядку вхідного файлу міститься натуральне число (1 \le N \le 200000), де - довжина . У другому рядку записана префікс-функція рядка .
Виведіть чисел - шукану -функцію.
Приклад 1