AT_s8pc_2_a.IOI列車で行こう2

IOI 列车是指按以下规则排序的列车：

• 只包含字母 I 和 O。
• 由 I 开头并结尾。
• I 和 O 交替出现。

如，$IOIOI$、$IOIOIOIOIOIOIOIOI$ 就是 IOI 列车。

现在，给定一个字符串 $S$。你要从中选取一些字符，使选取的字符按原来的排列顺序排列，恰好会组成 IOI 列车。

求满足以上条件时，操作后 IOI 列车长度的最大值。

一个只含有 I 和 O 的字符串 $S$。

一个整数，表示从字符串 $S$ 中选取字符后，字符串长度的最大值。若不能组成 IOI 列车，则输出 $0$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（30 pts）：$1 \leq \lvert S \rvert \leq 100$。
• Subtask 2（70 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \leq \lvert S \rvert \leq 50000$。

样例解释

#1：选取第 $1,2,4,6,7,8,9,11,12$ 个字符可以形成最长的 IOI 列车。

#2：选取第 $1,2,3,4,5,7,8,9,10$ 个字符可以形成最长的 IOI 列车。