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