Копыто, Бумага, Ножницы (Серебро)
Возможно Вы слышали об игре "Камень, Бумага, Ножницы". Коровы любят играть в похожую игру "Копыто, Бумага, Ножницы" Правила игры "Копыто, Бумага, Ножницы" просты. Две коровы играют друг против друга. Они обе считают до трёх, а затем одновременно делают жест, представляющий копыто, бумагу или ножницы. Копыто выигрывает у ножниц, ножницы выигрывают у бумаги, бумага выигрывает у копыта. Конечно может быть и ничья, если обе коровы сделали один и тот же жест.
Фермер Джон хочет сыграть с Бесси n раз. Бесси будучи экспертом в этой игре может предсказать каждый из жестов ФД. Но как корова, она очень ленива. Поэтому она хочет играть одним и тем же жестом переключившись на другой не более одного раза за все игры. Например, она может играть "Копыто" первые x игр, и затем переключится на "бумагу" на оставшиеся n − x игр.
По заданной последовательности жестов ФД, определите максимальное количество игр, которое выиграет Бесси.
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 10^5). Оставшиеся n строк содержат жесты ФД, представленные символами H, P, S.
Выходные данные
Выведите максимальное количество игр, которое может выиграть Бесси, если она может переключать жест не более одного раза.