Шахтарі
Є дві копальні, у кожній з яких працює група шахтарів. Видобування вугілля - важка робота, тому для її виконання шахтарям потрібна їжа. Кожен раз, коли контейнер з їжею привозять до копальні, шахтарі видобувають деяку кількість вугілля. Є три типи контейнерів: контейнер з м'ясом, контейнер з рибою і контейнер з хлібом.
Шахтарі люблять різноманітність у раціоні, і їхня робота буде більш продуктивною, якщо їжа різноманітна. У момент надходження чергового контейнера з їжею до копалень, залежно від типів контейнера, що надійшов, і попередніх двох (або меншої кількості, якшо всього до цієї копальні надійшло менше трьох контейнерів) шахтарі цієї копальні приймають одне з трьох рішень:
- якщо всі розглянуті контейнери були одного типу, то шахтарі видобувають одну одиницю вугілля;
- якщо розглянуті контейнери були двох різних типів, то шахтарі видобувають дві одниці вугілля;
- якщо розглянуті контейнери були всіх трьох різних типів, то шахтарі видобувають три одиниці вугілля.
Відомо, контейнери яких типів будуть відправлені і в якому порядку. Можна впливати на кількість вугілля, що видобувається, відповідним чином визначаючи, до якої з копалень буде відправлено черговий контейнер. Контейнери не можна розділяти на частини, кожен контейнер має бути цілком відправлений до однієї з копалень.
Зовсім не обов'язково, щоб до обох копалень надійшла однакова кількість контейнерів (наприклад, дозволяється відправляти всі контейнери до однієї копальні).
Вашій програмі будуть надані типи контейнерів у тому порядку, у якому вони будуть відправлені. Напишіть програму, яка визначає максимальну сумарну кількість вугілля, яку можна видобути (на обох копальнях), розподіляючи, які контейнери необхідно відправити до першої, а які - до другої.
Вхідні дані
Перший рядок вхідних даних містить ціле число n (1 ≤ n ≤ 100 000), кількість контейнерів.
Другий рядок містить рядок з n символів - типи контейнерів у тому порядку, у якому вони будуть відправлені. Кожен із цих символів може бути однією з великих літер "M" (м'ясо), "F" (риба) або "B" (хліб).
Вихідні дані
Виведіть ціле число - максимальну сумарну кількість вугілля, яку можна видобути.