Задачі
A-функція від рядка
A-функція від рядка
Дано рядок S, який складається з n символів. Визначимо функцію A(i) від перших i символів цього рядка наступним чином: A(i) дорівнює такому максимально можливому k, що наступні рядки рівні:
S[1] + S[2] + S[3] + ... + S[k],
S[i] + S[i-1] + S[i-2] + ... + S[i-k+1],
де **S[i] - i-ий символ рядка S, а знак + означає, що символи записуються у рядок безпосередньо один за одним.
Напишіть програму, яка обчислить значення функції A для заданого рядка для всіх можливих значень i від 1 до n.
Вхідні дані
У першому рядку записано одне число n (1 ≤ n ≤ 200000). У другому рядку записано рядок довжиною n символів, що складається лише з великих і (або) маленьких латинських літер.
Вихідні дані
Виведіть n чисел - значення функції A(1), A(2), ..., A(n).
Приклад
Вхідні дані #1
5 aabaa
Вихідні дані #1
1 2 0 1 5