A - IOI列車で行こう2

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

E869120国ではIOI国に続き, 新たに鉄道を敷設した。

E869120国の鉄道を走る列車はいくつかの車両が連結されたものであり, 車両には I, O の 2 種類がある。

しかし, 次のような規則でつながなければならない。

  • 車両はそれぞれ異なる種類の車両としか連結できない。
  • 列車に運転席を設ける関係上,列車の両端の車両は種類 I でなければならない。

列車は車両の種類を表す文字を順につなげた文字列で表され, 列車の長さはその文字列の長さであるとする。

例えば, IOIOI , IOIOIOIOIOIOIOIOI などが条件を満たす。

今, 車庫には文字列 S で表されるような車両が連結された状態がある。

編成する車両は, S の部分列でなければならない。

そのとき, 最大で何両の列車が編成できるだろうか。


入力

入力は以下の形式で標準入力から与えられる。

S
  • 1 行目には、車庫の状態を表す文字列 S が与えられる。

出力

出力は以下の形式で標準出力に従うこと。

  • 編成できる車両の両数を 1 行で出力せよ。
  • ただし, 列車が編成できない場合は 0 と出力せよ。

制約

  • 1≦|S|≦50,000

小課題

小課題 1 [ 25 点 ]

  • 1 ≦ | S | ≦ 100 を満たす。

小課題 2 [ 75 点 ]

  • 追加の制約はない。

入力例1

IOOIIOIOIIOI

出力例1

9
  • 1, 2, 4, 6, 7, 8, 9, 11, 12 両目を選べば, 列車「 IOIOIOIOI 」が作れます。

入力例2

IOIOIIOIOI

出力例2

9
  • 1, 2, 3, 4, 5, 7, 8, 9, 10 両目を選べば, 列車「 IOIOIOIOI 」が作れます。

入力例3

IIOOII

出力例3

3

問題文担当者:square1001