KOIOI 타워는 원반을 사용하는 혼자서 할 수 있는 게임이다.
이 게임은, K, O, I 중 하나의 문자가 쓰여진 어떤 원반을 이용한다.
원반은 직경이 서로 다르며 게임 시작에는 원반들이 직경이 큰 것부터 순서대로 아래에서 위로 향해 쌓여있다.

 

쭈노는 이러한 원반을 이용하여 가능한 많은 KOIOI 타워를 만들고 싶다. KOIOI 타워는 3 장의 원반으로 구성되며, 원반의 직경이 작은 것부터 순서대로 읽을 때 KOI 또는 IOI로 읽을 것이다. 또한 같은 접시를 두 번 이상 사용할 수 없다.

 

원반에 쓰여진 문자가 각각 원반의 직경이 작은 것으로부터 순서대로 길이 N의 문자열 S로 주어진다. 이 원반을 사용하여 만들 수 있는 KOIOI 타워의 개수의 최대 값을 구하는 프로그램을 작성하라.

 

그림 : KOIOII에서 KOIOI 타워 2 개 만들 수 있다.

 

첫 행에 문자열의 길이 N 이 입력된다.( 1 <= N <= 1,000,000) 다음 행에 문자열 S가 입력된다.

조건을 만족하며 만들 수 있는 KOIOI 타워의 최대 개수를 출력한다.

6
KOIIOI

2

5
KOIOI

1

6
KOIOII

2

15
KKOIIOOKOKIOIIO

4