스탬프 랠리 2

JOI 상점가에는 큰길을 따라 상점 $N$개가 늘어서 있고, 상점가 입구에서 출구 쪽으로 차례대로 $1, 2, \dots, N$번이 붙어 있다. 상점가는 일방통행이라 입구에서 출구 방향으로만 이동한다.

지역을 알리려고 JOI 상점가에서 스탬프 랠리를 연다. 각 상점은 J, O, I 중 하나를 스탬프로 준비하고, 그 상점에서 물건을 산 사람은 스탬프 카드에 그 상점의 스탬프를 받는다. 스탬프 랠리에 참가하는 사람은 상점 정확히 세 곳에 들어간다. 입구에서 칸이 세 개인 스탬프 카드를 나눠 주고, 첫 번째로 들어간 상점, 두 번째로 들어간 상점, 세 번째로 들어간 상점의 스탬프를 그 순서대로 받는다. 출구에서 스탬프 카드를 걷어서, 찍힌 스탬프가 먼저 들어간 상점부터 차례대로 J, O, I이면 상품권을 준다. 스탬프의 종류나 순서가 다르면 상품권을 받지 못한다.

상점가가 일방통행이므로 고른 상점 세 곳은 언제나 번호가 작은 쪽부터 방문한다. 그래서 상품권을 받는 선택은 $i < j < k$이고 상점 $i$, 상점 $j$, 상점 $k$의 스탬프가 차례대로 J, O, I인 상점 세 곳의 조합이다.

이미 상점 $N$개는 어떤 스탬프를 준비할지 모두 정했지만, JOI 상점가에 상점 하나를 새로 내기로 했고 그 자리와 그 상점이 준비할 스탬프를 정해야 한다. 새 상점을 낼 자리는 상점 $i$와 상점 $i+1$ 사이 ($1 \le i \le N-1$), 입구와 상점 $1$ 사이, 상점 $N$과 출구 사이 가운데 하나로 정한다. 새 상점의 스탬프는 J, O, I 세 가지 중 하나로 정한다. 참가자는 새 상점에도 들어갈 수 있다.

상품권을 받는 상점 선택의 수가 많을수록 스탬프 랠리가 잘된다고 상점가는 생각한다. 새 상점의 자리와 스탬프를 정했을 때 나오는 이 선택의 수의 최댓값을 구하여라.

표준 입력에서 다음을 읽어라.

• 첫째 줄에 정수 $N$이 주어진다. JOI 상점가에 지금 상점이 $N$개 있다는 뜻이다.
• 둘째 줄에 알파벳 대문자 J, O, I로만 이루어진 길이 $N$의 문자열 $S$가 주어진다. $S$의 왼쪽에서 $i$번째 문자 ($1 \le i \le N$)는 상점 $i$가 준비한 스탬프의 종류다.

상품권을 받는 상점 선택의 수의 최댓값을 표준 출력에 한 줄로 출력하여라.

이 수가 32비트 부호 있는 정수의 범위에 들어간다는 보장은 없으니 주의하여라.

• $3 \le N \le 100000$
• $S$는 J, O, I로만 이루어진 길이 $N$의 문자열이다.