문제 설명

JOI 본선을 향해 프로그래밍 연습을 하던 당신은 올해 JOI 예선 문제에는 수치 문제만 있고 문자열 문제가 없었다는 것을 깨달았다. 그래서 당신은 남몰래 문자열 문제에 강해져서 라이벌들과 격차를 벌리기로 했다. 과거 JOI 문제를 살펴보니, J, O, I의 $3$종류의 문자로 이루어진 문자열에 익숙해져야 할 것 같다는 사실을 알게 되었다. 그래서 그러한 문자열에 대해 생각해 보기로 했다. 당신은 "주어진 문자열이 부분 문자열로 JOI를 가지는지 답하라"라는 문제를 떠올렸지만, 이는 금방 풀려 버렸다. 더 높은 수준의 문제를 풀고 싶었던 당신은 다음과 같은 문제를 만들었다.

문자열 $t$가 문자열 $s$의 부분 문자열이라는 것은, $t$의 맨 앞과 맨 뒤에 몇 글자($0$글자여도 됨)를 덧붙이면 $s$가 된다는 것이다. 예를 들어, JJOOII는 OJJOOIIOJOI의 부분 문자열이다. 반면, JOI는 JOOI의 부분 문자열이 아니다.

또한, $0$ 이상의 정수 $k$에 대하여, 레벨 $k$의 JOI 열이란 $k$개의 문자 J, $k$개의 문자 O, $k$개의 문자 I를 이 순서대로 나열한 문자열을 말한다. 예를 들어, JJOOII는 레벨 $2$의 JOI 열이다.

주어진 문자열의 부분 문자열인 JOI 열 중에서 레벨이 최대인 것을 구하고 싶다.

과제

J, O, I의 $3$종류의 문자로 이루어진 길이 $N$의 문자열 $S$가 주어졌을 때, 레벨 $k$의 JOI 열이 $S$의 부분 문자열이 되도록 하는 최대의 $k$ 값을 구하는 프로그램을 작성하시오.

제한

• $1 \le N \le 1000000 \ (= 10^6)$: $S$의 길이.

입력

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

• $1$번째 줄에는 J, O, I의 $3$종류의 문자로 이루어진 문자열 $S$가 적혀 있다.

출력

표준 출력에 레벨 $k$의 JOI 열이 $S$의 부분 문자열이 되도록 하는 최대의 $k$ 값을 나타내는 정수를 $1$줄로 출력하시오.

채점 기준

• 채점용 데이터 중 배점의 $20\%$에 해당하는 데이터는 $N \le 100$을 만족한다.

입출력 예 1

입력

OJJOOIIOJOI

출력

2

OJJOOIIOJOI는 레벨 $2$의 JOI 열인 JJOOII를 부분 문자열로 포함하며, 레벨 $3$ 이상의 JOI 열은 부분 문자열로 포함하지 않는다.

입출력 예 2

입력

IJJIIJJJ

출력

0

레벨 $0$의 JOI 열이란 길이 $0$인 문자열이다.

입출력 예 3

입력

JOIJOIJOIJOIJOI

출력

1

입출력 예 4

입력

OOJJJJJJOOOOIIIII

출력

4