eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків

ABB

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Фернандо был нанят Университетом Ватерлоо для завершения проекта развития, который университет начал совсем недавно. За пределами кампуса университет хотел построить представительскую улицу бунгало для важных иностранных посетителей и сотрудников.

В настоящее время улица застроена лишь частично, она начинается на берегу озера и продолжается к лесу, где и заканчивается. Задача Фернандо — закончить улицу в конце леса, построив там некоторое количество бунгало. Все существующие бунгало стоят на одной стороне улицы, а новые должны быть построены на той же стороне. Бунгало бывают разных типов и окрашены в разные цвета.

Вся улица кажется Фернандо немного хаотичной. Он боится, что это будет выглядеть еще более хаотично, когда он добавит новые бунгало собственного дизайна. Чтобы уравновесить хаос всех форм бунгало, он хочет внести некоторый порядок в их расположение, выбрав подходящие цвета для новых бунгало. Когда проект будет завершен, вся последовательность цветов бунгало будет симметричной, то есть последовательность цветов будет одинаковой при наблюдении с любого конца улицы.

Среди других вопросов Фернандо задается вопросом, какое минимальное количество новых бунгало ему необходимо построить и покрасить надлежащим образом, чтобы завершить проект, соблюдая при этом установленные им самим ограничения на цвета бунгало.

Вхідні дані

В первой строке находится одно целое число n~(1 \le n \le 4 \cdot 10^5) — количество существующих бунгало на улице. В следующей строке описывается последовательность цветов существующих бунгало, начиная с начало улицы у озера. Строка содержит одну строку, состоящую из n строчных букв (от "a" до "z"), где разные буквы представляют разные цвета.

Вихідні дані

Выведите минимальное количество бунгало, которое нужно добавить в конец улицы и соответствующим образом покрасить, чтобы удовлетворить требования Фернандо по симметрии цвета.

Приклад

Вхідні дані #1
3
abb
Вихідні дані #1
1
Вхідні дані #2
12
recakjenecep
Вихідні дані #2
11
Вхідні дані #3
15
murderforajarof
Вихідні дані #3
6
Джерело 2019 ACM Central Europe (CERC), Прага, Ноябрь 29 - Декабрь 1, Задача A