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