Sətir funksiyalarının çevrilməsi

Sətir S üçün Z-funksiyasını aşağıdakı kimi təyin edək: Z[i] = lcp(S, S[i..|S|]), burada lcp(S[1], S[2]) sətirlərinin S[1] və S[2] ən uzun ümumi prefiksinin uzunluğuna bərabərdir. Məsələn, S = abacabaa üçün Z-funksiyası [8, 0, 1, 0, 3, 0, 1, 1] bərabərdir.

Sətir S üçün prefiks-funksiyasını belə təyin edək: pi[i] = max{k | 0 ≤ k < i, S[1..k] = S[i - k + 1..i]}. Məsələn, S = abacabaa üçün prefiks-funksiyası belədir: [0, 0, 1, 0, 1, 2, 3, 1].

Hər hansı bir sətir S üçün Z-funksiyası məlumdur, lakin sətir S itirilmişdir. Sizin vəzifəniz verilmiş Z-funksiyasına əsasən prefiks-funksiyasını tapmaqdır.

Giriş məlumatları

Girişin ilk sətirində təbii ədəd N (1 ≤ N ≤ 200000) verilir, burada N - S sətirinin uzunluğudur. İkinci sətirdə S sətirinin Z-funksiyası verilir.

Çıxış məlumatları

N ədədini çıxış edin - axtarılan prefiks-funksiyası.