Шахтеры
Есть два рудника, в каждой из которых работает группа шахтеров. Добыча угля - тяжелый труд, поэтому для её выполнения шахтерам нужна еда. Каждый раз, когда контейнер с едой привозят к руднику, шахтеры добывают некоторое количество угля. Есть три типа контейнеров: контейнер с мясом, контейнер с рыбой и контейнер с хлебом.
Шахтеры любят разнообразие в рационе, и их труд будет более производительным, если еда разнообразна. В момент поступления очередного контейнера с едой к руднику, зависимо от типов контейнера, что поступил, и предыдущих двух (или меньшего количества, если всего к этому руднику поступило менее трёх контейнеров) шахтеры этого рудника принимают одни из трех решений:
если все рассмотренные контейнеры были одного типа, то шахтеры добывают одну единицу угля;
если рассмотренные контейнеры были двух разных типов, то шахтеры добывают две единицы угля;
если рассмотренные контейнеры были всех трех разных типов, то шахтеры добывают три единицы угля.
Известно, контейнеры каких типов будут отправлены и в каком порядке. Можно влиять на количество добываемого угля, соответствующим образом определяя, к какому из рудников будет отправлено очередной контейнер. Контейнеры нельзя разделять на части, каждый контейнер должен быть целиком отправлен к одному из рудников.
Вовсе не обязательно, чтобы к обеим рудникам поступило одинаковое количество контейнеров (например, разрешается отправлять все контейнеры к одному руднику).
Вашей программе будут заданы типы контейнеров в том порядке, в каком они будут отправлены. Напишите программу, которая определяет максимальное суммарное количество угля, которое можно добыть (на обеих рудниках), распределяя, какие контейнеры необходимо отправить к первому, а какие - ко второму.
Входные данные
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 100000), количество контейнеров.
Вторая строка содержит строку из n символов - типы контейнеров в том порядке, в котором они будут отправлены. Каждый из этих символов может быть одной с больших букв "M" (мясо), "F" (рыба) или "B" (хлеб).
Выходные данные
Выведите целое число - максимальное суммарное количество угля, которое можно добыть.