문제
KOIOI 타워는 원반을 사용하는 혼자서 할 수 있는 게임이다. 이 게임은, K, O, I 중 하나의 문자가 쓰여진 어떤 원반을 이용한다. 원반은 직경이 서로 다르며 게임 시작에는 원반들이 직경이 큰 것부터 순서대로 아래에서 위로 향해 쌓여있다.
쭈노는 이러한 원반을 이용하여 가능한 많은 KOIOI 타워를 만들고 싶다. KOIOI 타워는 3 장의 원반으로 구성되며, 원반의 직경이 작은 것부터 순서대로 읽을 때 KOI 또는 IOI로 읽을 것이다. 또한 같은 접시를 두 번 이상 사용할 수 없다.
원반에 쓰여진 문자가 각각 원반의 직경이 작은 것으로부터 순서대로 길이 N의 문자열 S로 주어진다. 이 원반을 사용하여 만들 수 있는 KOIOI 타워의 개수의 최대 값을 구하는 프로그램을 작성하라.
입력
첫 행에 문자열의 길이 N 이 입력된다.( 1 <= N <= 1,000,000)
다음 행에 문자열 S가 입력된다.
출력
조건을 만족하며 만들 수 있는 KOIOI 타워의 최대 개수를 출력한다.
예제1
입력
6
KOIIOI
출력
2
예제2
입력
5
KOIOI
출력
1
예제3
입력
6
KOIOII
출력
2
예제4
입력
15
KKOIIOOKOKIOIIO
출력
4
출처
JOI 2012/2013 본선 4