Задача №111134. Шахтеры
На двух угольных шахтах работают шахтеры. Добыча угля — тяжелая работа, так что шахтерам необходимо доставлять еду прямо в шахты. Каждый раз, когда очередная порция продовольствия доставляется в шахту, шахтеры производят некоторое количество угля. Существует три типа еды для шахтеров: мясо, фрукты и бублики. Шахтеры любят разнообразие в еде и будут работать продуктивнее, если их диета будет разнообразной. Точнее, каждый раз, когда в шахту доставляется новая порция продовольствия, необходимо посмотреть на две предыдущие поставки (или меньше чем две, если их еще не было) и действовать по следующему правилу:
- если вся еда была одинаковой — будет произведена одна тонна угля
- если еды была двух типов — будет произведено две тонны угля
- если трех типов — три тонны угля
Тип и порядок поставок еды известен. Однако, можно выбрать, на какую из двух шахт какую поставку отправить. Поставка не может быть разделена и обязательно должна быть доставлена на первую или вторую шахту. Две шахты не обязательно должны получить одинаковое количество поставок (например, все поставки могут идти на одну шахту). По известному порядку и типу поставок необходимо написать программу, определяющую максимально возможное количество тонн угля, которое можно добыть на обеих шахтах, при наилучшем распределении поставок между первой и второй шахтой.
Первая строка содержит число N (1 ≤ N ≤ 100 000) — количество поставок еды. Вторая строка содержит N символов — типы поставок в том порядке, в котором они будут осуществляться. Каждый из символов будет большой латинской буквой M (мясо), F (фрукты) или B (бублики).
Выведите единственное число — количество тонн угля, которое можно добыть.
6
MBMFFB
12
16
MMBMBBBBMMMMMBMB
29