문제 설명

JOIOI의 탑이란 $1$명이서 노는 원판을 사용한 게임이다.

이 게임은 J, O, I 중 어느 한 글자가 적힌 몇 개의 원판을 사용하여 진행한다. 원판은 지름이 서로 다르며, 게임 시작 시에는 이러한 원판들이 지름이 큰 것부터 순서대로 아래에서 위로 쌓여 있다. 당신은 이 원판들을 사용하여 가능한 한 많은 미니 JOIOI의 탑을 만들고 싶다. 미니 JOIOI의 탑이란 $3$장의 원판으로 이루어지며, 원판의 지름이 작은 것부터 순서대로 읽었을 때 JOI 혹은 IOI로 읽히는 것이다. 단, 같은 원판을 $2$번 이상 사용할 수는 없다.

그림: JOIOII로부터는 미니 JOIOI의 탑을 $2$개 만들 수 있다

과제

준비된 원판에 적힌 글자가 각각 원판의 지름이 작은 것부터 순서대로 길이 $N$인 문자열 $S$로 주어진다. 이 원판들을 사용하여 만들 수 있는 미니 JOIOI의 탑의 개수의 최댓값을 구하는 프로그램을 작성하시오.

제한

• $1 \le N \le 1000000$: 문자열 $S$의 길이.

입력

표준 입력으로부터 다음 데이터를 읽어들이시오.

• $1$번째 줄에는 정수 $N$이 적혀 있다. $N$은 문자열 $S$의 길이를 나타낸다.
• $2$번째 줄에는 문자열 $S$가 적혀 있다.

출력

표준 출력에 만들 수 있는 미니 JOIOI의 탑의 수의 최댓값을 나타내는 정수를 $1$줄로 출력하시오.

채점 기준

• 채점용 데이터 중 배점의 $10\%$에 해당하는 데이터는 $N \le 15$를 만족한다.
• 채점용 데이터 중 배점의 $30\%$에 해당하는 데이터는 $N \le 50$을 만족한다.
• 채점용 데이터 중 배점의 $50\%$에 해당하는 데이터는 $N \le 3000$을 만족한다.

입출력 예 1

입력

6
JOIIOI

출력

2

JOIIOI는 JOI 및 IOI를 각각 $1$개씩 부분 수열로 포함하고 있으므로, 만들 수 있는 미니 JOIOI의 탑은 $2$개이다.

입출력 예 2

입력

5
JOIOI

출력

1

부분 수열로 JOI 및 IOI를 포함하고 있지만, 글자를 $2$번 이상 사용할 수는 없기 때문에 동시에 꺼낼 수는 없다.

입출력 예 3

입력

6
JOIOII

출력

2

이 입출력 예제는 문제 설명의 예시에 해당한다.

입출력 예 4

입력

15
JJOIIOOJOJIOIIO

출력

4