0267 - JJOOII

問題

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 ≤ N ≤ 1000000 (= 10⁶)   S の長さ

入力

標準入力から以下のデータを読み込め．

• 1 行目にはJ, O, I の3 種類の文字からなる文字列S が書かれている．

出力

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

採点基準

採点用データのうち，配点の20%分については，N ≤ 100 を満たす．

入出力例

OJJOOIIOJOI

2

OJJOOIIOJOI はレベル2 のJOI 列であるJJOOII を部分文字列として含んでおり，レベル3 以上のJOI列は部分文字列として含まない．

IJJIIJJJ

0

JOIJOIJOIJOIJOI

1

OOJJJJJJJOOOOIIIII

4