문제

당신은 "가위, 바위, 보"라는 게임을 들어보았을 것이다. 충남대학교 알고리즘 동아리의 유진이는 이와 유사한 "발굽, 종이, 가위"라는 게임을 현성이와 함께 하려고 한다.

"발굽, 종이, 가위"의 규칙은 간단하다. 두 사람이 동시에 발굽(H), 종이(P), 가위(S) 중 하나를 나타내는 제스처를 취한다. 발굽은 가위를 이기고(발굽으로 가위를 부술 수 있다), 가위는 종이를 이기며(가위로 종이를 자를 수 있다), 종이는 발굽을 이긴다(발굽이 종이에 베일 수 있다). 예를 들어, 첫 번째 사람이 "발굽"을 내고 두 번째 사람이 "종이"를 냈다면 두 번째 사람이 이긴다. 두 사람이 같은 제스처를 냈다면 비긴다.

유진이는 현성이와 총 $N$번의 게임을 할 예정이다. ($1 \le N \le 100\,000$) 게임의 고수인 현성이는 유진이가 각 판에 어떤 제스처를 낼지 미리 모두 예측할 수 있다. 하지만 현성이는 매우 게을러서, 전체 게임 동안 제스처를 최대 한 번까지만 바꾸려고 한다. 즉, 처음 $x$번의 게임 동안은 한 가지 제스처를 계속 내다가, 나머지 $N-x$번의 게임 동안은 다른 제스처를 내는 방식이다. 물론 게임 내내 단 한 가지 제스처만 사용할 수도 있다.

유진이가 낼 $N$개의 제스처 순서가 주어질 때, 현성이가 이길 수 있는 최대 게임 수를 구하시오.

입력

첫째 줄에 게임의 횟수 $N$이 주어진다. ($1 \le N \le 100\,000$)

이어서 $N$개의 줄에 유진이가 각 판에 낼 제스처가 한 줄에 하나씩 주어진다. 제스처는 H (발굽), P (종이), S (가위) 중 하나이다.

출력

현성이가 제스처를 최대 한 번만 바꿀 수 있을 때, 이길 수 있는 최대 게임 수를 출력한다.

예제 입력 1

5
P
P
H
P
S

예제 출력 1

4