Возможно Вы слышали об игре "Камень, Бумага, Ножницы". Коровы любят играть в похожую игру "Копыто, Бумага, Ножницы"
Правила игры "Копыто, Бумага, Ножницы" просты. Две коровы играют друг против друга. Они обе считают до трёх, а затем одновременно делают жест, представляющий копыто, бумагу или ножницы. Копыто выигрывает у ножниц, ножницы выигрывают у бумаги, бумага выигрывает у копыта. Конечно может быть и ничья, если обе коровы сделали один и тот же жест.
Фермер Джон хочет сыграть с Бесси \(N\) раз (\(1 \leq N \leq 100,000\)).
Бесси будучи экспертом в этой игре может предсказать каждый из жестов ФД.
Но как корова, она очень ленива. Поэтому она хочет играть одним и тем же жестом
переключившись на другой не более одного раза за все игры. Например, она может играть
"Копыто" первые \(x\) игр, и затем переключится на "бумагу" на оставшиеся \(N-x\) игр.
По заданной последовательности жестов ФД, определите максимальное
количество игр, которое выиграет Бесси.
ФОРМАТ ВВОДА (файл hps.in):
Первая строка ввода содержит число
\(N\).
Оставшиеся \(N\) строк содержат жесты ФД, представленные символами H, P, S.
ФОРМАТ ВЫВОДА (файл hps.out):
Выведите максимальное количество игр, которое может выиграть Бесси,
если она может переключать жест не более одного раза.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
P
P
H
P
S
|
4
|