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