Sətir funksiyalarının çevrilməsi: tərs məsələ#4907
Для sətir S üçün Z-funksiyanı aşağıdakı kimi təyin edək: Z[i] = lcp(S, S[i..|S|]), burada lcp(S[1], S[2]) sətirlər S[1] və S[2] üçün ən uzun ümumi prefiksin uzunluğuna bərabərdir. Məsələn, S = abacabaa üçün Z-funksiya [8, 0, 1, 0, 3, 0, 1, 1] bərabərdir.
Sətir S üçün onun prefiks-funksiya 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 onun prefiks-funksiya belədir: [0, 0, 1, 0, 1, 2, 3, 1].
Hər hansı bir sətir S üçün onun prefiks-funksiya qurulmuşdur, lakin sətir S itirilmişdir. Sizin vəzifəniz verilmiş prefiks-funksiya əsasında onun Z-funksiyasını əldə etməkdir.
Giriş faylının birinci sətirində təbii ədəd N (1 ≤ N ≤ 200000) verilir, burada N - S-in uzunluğudur. İkinci sətirdə sətir S-in prefiks-funksiyası yazılmışdır.
Z-funksiyanı təşkil edən N ədədini çıxış edin.
Nümunə 1