Для рядка 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-функцію.