JOIOI 탑

JOIOI 탑은 원반을 쌓아 혼자 즐기는 게임이다.

게임에는 각각 문자 J, O, I 중 하나가 적힌 원반을 사용한다. 모든 원반의 반지름은 서로 다르며, 처음에는 반지름이 가장 큰 원반이 맨 아래에 오도록 위로 갈수록 반지름이 작아지는 순서로 쌓여 있다.

이 원반들로 가능한 한 많은 미니 JOIOI 탑을 만들려고 한다. 미니 JOIOI 탑은 원반 3개로 이루어지며, 반지름이 작은 원반부터 문자를 읽었을 때 JOI 또는 IOI가 되어야 한다. 한 원반은 최대 하나의 탑에만 속할 수 있다. 탑을 이루는 세 원반이 원래 쌓인 순서에서 반드시 인접해 있을 필요는 없다.

반지름이 작은 원반부터 순서대로 각 원반에 적힌 문자가 주어질 때, 만들 수 있는 미니 JOIOI 탑의 최대 개수를 구하시오.

첫째 줄에 원반의 개수 $N$이 주어진다. $(1 \le N \le 1,000,000)$

둘째 줄에 각 원반에 적힌 문자가 반지름이 작은 순서대로 공백 없이 주어진다. 각 문자는 J, O, I 중 하나이다.

만들 수 있는 미니 JOIOI 탑의 최대 개수를 첫째 줄에 출력한다.