시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 25 6 6 31.579%

문제

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 行目には J, O, I の 3 種類の文字からなる文字列 S が書かれている.

制限

  • 1 ≤ N ≤ 1000000 (= 106) S の長さ

출력

標準出力に,レベル k の JOI 列が S の部分文字列であるような最大の k の値を表す整数を 1 行で出力せよ.

예제 입력

OJJOOIIOJOI

예제 출력

2

힌트