발굽, 보, 가위 (Silver)

"가위바위보" 게임은 아마 들어 봤을 것이다. 소들은 이와 비슷한 "발굽, 보, 가위"라는 게임을 즐긴다.

"발굽, 보, 가위"의 규칙은 간단하다. 소 두 마리가 서로 대결한다. 둘이 함께 셋을 센 다음, 동시에 발굽, 종이 한 장, 가위 중 하나를 나타내는 손짓을 한다. 발굽은 가위를 이기고(발굽으로 가위를 부술 수 있으므로), 가위는 보를 이기며(가위로 종이를 자를 수 있으므로), 보는 발굽을 이긴다(종이에 발굽이 베일 수 있으므로). 예를 들어 첫 번째 소가 "발굽"을, 두 번째 소가 "보"를 내면 두 번째 소가 이긴다. 물론 두 소가 같은 손짓을 내면 비길 수도 있다.

농부 존은 자신이 가장 아끼는 소 베시와 "발굽, 보, 가위"를 $N$판 하려고 한다($1 \le N \le 100{,}000$). 이 게임의 달인인 베시는 존이 손짓을 내기 전에 그 손짓을 모두 미리 알 수 있다. 아쉽게도 베시는 소라서 매우 게으르다. 그래서 같은 손짓을 여러 번 연달아 내는 경향이 있다. 사실 베시는 전체 게임을 통틀어 손짓을 많아야 한 번만 바꾸려 한다. 예를 들어 처음 $x$판은 "발굽"을 내다가, 남은 $N-x$판은 "보"로 바꿔 낼 수 있다.

존이 낼 손짓의 순서가 주어질 때, 베시가 이길 수 있는 게임 수의 최댓값을 구하여라.

첫째 줄에 $N$이 주어진다.

다음 $N$개의 줄에는 존의 손짓이 차례대로 하나씩 주어진다. 각 손짓은 H, P, S 중 하나이며 각각 발굽, 보, 가위를 뜻한다.

베시가 손짓을 많아야 한 번 바꿀 수 있을 때, 베시가 이길 수 있는 게임 수의 최댓값을 출력한다.