ABB#9759
Фернандо найняли Університетом Ватерлоо для завершення нещодавно розпочатого проекту. Університет планує за межами кампусу побудувати представницьку вулицю з бунгало для важливих іноземних гостей та співробітників.
Наразі вулиця забудована лише частково: вона починається біля берега озера і тягнеться до лісу, де й закінчується. Завдання Фернандо — завершити забудову вулиці, побудувавши ще кілька бунгало в її кінці, біля лісу. Усі вже побудовані будинки розташовані на одній стороні вулиці, і нові бунгало мають бути розміщені на тій самій стороні. Існуючі бунгало відрізняються за типом і пофарбовані в різні кольори.
На погляд Фернандо, вулиця виглядає дещо хаотично. Він побоюється, що нові будинки, виконані за його власним дизайном, лише посилять це враження. Щоб внести елемент порядку, він вирішив підібрати такі кольори для нових бунгало, щоб уся кольорова послідовність будинків на вулиці стала симетричною. Це означає, що послідовність кольорів повинна читатися однаково з обох кінців вулиці.
Серед інших завдань Фернандо цікавить, яку мінімальну кількість нових бунгало необхідно побудувати і пофарбувати відповідним чином, щоб завершити проект відповідно до задуманої симетрії.
У першому рядку задано ціле число n~(1 \le n \le 4 \cdot 10^5) — кількість вже побудованих бунгало.
У другому рядку дано послідовність їхніх кольорів у порядку від початку вулиці біля озера. Це рядок довжиною , що складається зі строкових латинських літер від '' до '', кожна з яких позначає певний колір.
Виведіть мінімальну кількість бунгало, які потрібно додати в кінець вулиці і пофарбувати відповідним чином, щоб уся кольорова послідовність стала симетричною.
Приклад 1
Приклад 2
Приклад 3