AT_s8pc_2_a IOI列車で行こう2

[problemUrl]: https://atcoder.jp/contests/s8pc-2/tasks/s8pc_2_a E869120国ではIOI国に続き, 新たに鉄道を敷設した。 E869120国の鉄道を走る列車はいくつかの車両が連結されたものであり, 車両には $ I $, $ O $ の 2 種類がある。 しかし, 次のような規則でつながなければならない。 - 車両はそれぞれ異なる種類の車両としか連結できない。 - 列車に運転席を設ける関係上，列車の両端の車両は種類 $ I $ でなければならない。 列車は車両の種類を表す文字を順につなげた文字列で表され, 列車の長さはその文字列の長さであるとする。 例えば, $ IOIOI $ , $ IOIOIOIOIOIOIOIOI $ などが条件を満たす。 今, 車庫には文字列 $ S $ で表されるような車両が連結された状態がある。 編成する車両は, $ S $ の部分列でなければならない。 そのとき, 最大で何両の列車が編成できるだろうか。 - $ 1,\ 2,\ 4,\ 6,\ 7,\ 8,\ 9,\ 11,\ 12 $ 両目を選べば, 列車「 $ IOIOIOIOI $ 」が作れます。 - $ 1,\ 2,\ 3,\ 4,\ 5,\ 7,\ 8,\ 9,\ 10 $ 両目を選べば, 列車「 $ IOIOIOIOI $ 」が作れます。

入力は以下の形式で標準入力から与えられる。 > $ S $ - $ 1 $ 行目には、車庫の状態を表す文字列 $ S $ が与えられる。

出力は以下の形式で標準出力に従うこと。 - 編成できる車両の両数を $ 1 $ 行で出力せよ。 - ただし, 列車が編成できない場合は $ 0 $ と出力せよ。

### 制約 - $ 1≦ $|$ S $|$ ≦50,000 $ ### 小課題 小課題 $ 1 $ \[ $ 25 $ 点 \] - $ 1 $ ≦ | $ S $ | ≦ $ 100 $ を満たす。 小課題 $ 2 $ \[ $ 75 $ 点 \] - 追加の制約はない。