JOIOI 탑

JOIOI 탑은 원반을 이용해서 혼자 재미있게 놀 수 있는 게임이다.

이 게임은 J, O, I중 하나의 문자가 쓰여진 원반을 이용한다. 원반은 모두 반지름이 다르다. 가장 처음에 원반은 반지름이 큰 것이 가장 아래에 있고, 나머지는 작아지는 순서대로 쌓여 있다.

상근이는 이 원반을 이용해 가능한 많은 미니 JOIOI 탑을 만들려고 한다. 미니 JOIOI 탑은 3개의 원반으로 구성되며, 반지름이 작은 것부터 읽었을 때 JOI나 IOI이어야 한다. 한 미니 JOIOI 탑에 속한 원반은 다른 탑에 속할 수 없다.

반지름이 작은 원반부터 순서대로 원반에 적혀져 있는 문자가 순서대로 주어진다. 이때, 만들 수 있는 미니 JOIOI 탑의 최대 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 원반의 개수 N이 주어진다. 둘째 줄에는 원반에 적혀있는 문자가 반지름이 작은 순서대로 주어진다. (1 ≤ N ≤ 1,000,000)

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