Для рядка 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 була порахована її Z-функція, а рядок S було втрачено. Ваша задача отримати його префікс-функцію за заданою Z-функцією.

Вхідні дані

У першому рядку вхідного файлу міститься натуральне число N (1 ≤ N ≤ 200000), де N - довжина S. У другому рядку записано Z-функцію рядка S.

Вихідні дані

Виведіть N чисел - шукану префікс-функцію.