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

Шахтарі

Шахтарі

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

На двох вугільних шахтах працюють шахтарі, продуктивність яких напряму залежить від різноманітності їжі, яку вони споживають.

Їжа приходить на шахти коробками і буває трьох типів: м'ясо, риба і хліб (да-да, ви можете поностальгувати, якщо десять років назад грали у "Settlers II"). Коли на шахту приходить чегова коробка з їжею, шахтері добувають деяку кількість вугілля, яка залежить від вмісту цієї коробки, а також від двох попередніх коробок, які вони отримували (або менше ніж двох, якщо вони ствльки ще не отримали), наступним чином:

  • Якщо всі ці три (або менше) коробки одного типу, вони добувають одну одиницю вугілля;

  • Якщо серед цих трьох (або менше) коробок два типи їжі, вони добувають дві одиниці вугілля;

  • Якщо серед цих трьох коробок всі три типи їжі, вони добувають три одиниці вугілля.

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

Коробки не можна "відкладувати на потім", а також ділити на частини: отримана коробка повинна бути тут же відправлена або на першу шахту, або на другу. Число коробок, які доставляються на кожну з шахт може бути довільним, навіть таким, що всі коробки можна відправити на одну шахту, якщо це вигідно для справи. (Доречі, якщо ви у майбутньому станете держ. службовцем, так вчиняти так як раз не потрібно!)

Вхідні дані

У першому рядку вхідного файлу міститься число n — кількість коробок їжі (1n100000), у другому — рядок довжини n, який складається з символів "M", "F" і "B", які позначають, відповідно, коробку з м'ясом, рибою і хлібом, і наведених у тому порядку, у якому коробки будуть поставлятись.

Вихідні дані

Виведіть одне число — максимальну кількість вугілля, яку зможуть видобути шахтарі при даних умовах.

Приклад

Вхідні дані #1
6 
MBMFFB
Вихідні дані #1
12
Автор Михайло Дворкін
Джерело Зимова Школа, Харків 2011, День 3