B4426 [CSP-X2025 山东] IOI 串

小明对字符串 `IOI` 怀有特殊的感情，他定义一种由大写英文字母 `I` 和 `O` 构成的字符串为“好串”，当且仅当它可以被划分为三个非空部分，依次为： 第一部分：连续非零个 `I` 第二部分：连续非零个 `O` 第三部分：连续非零个 `I` 如： `IIIOOIIII` 是一个好串，`IOI` 也是一个好串； `OIOI`，`IIO` 都不是好串。 现在，小明有一个长度为 $n$ 的字符串 $S$，且 $S$ 仅包含字符 `I` 和 `O`。 他可以进行任意次修改操作，每一次操作可将字符串中某一个位置的字符替换成另一个字符（即把 `I` 改为 `O`，或把 `O` 改为 `I`）。 例如： 当 $S = \tt{IIIOOOIOOII}$ 时，根据上述定义，$S$ 不是一个“好串”，但小明可以有多种方法通过修改操作把 $S$ 变为“好串”： 方法 1：把第 7 个字符 `I` 改为 `O`，经过 1 次操作得到 `IIIOOOOOOII`； 方法 2：分别把第 8 个和第 9 个字符 `O` 改为 `I`，经过 2 次操作得到 `IIIOOOIIIII`。 可以确定，至少经过 1 次修改操作才能把上面的字符串 $S$ 变为“好串”。 你的任务： 告诉你小明的字符串 $S$，请你帮小明计算，至少需要进行多少次修改操作，才能将字符串 $S$ 变为一个“好串”。如果 $S$ 已经是一个“好串”，输出 $0$。

一行，仅由 `I` 和 `O` 两种字符组成的字符串 $S$。

一行，包含一个整数，表示把字符串 $S$ 修改为“好串”需要的最少的修改次数。

【样例 3】 见选手目录下的 `ioi/ex_ioi3.in` 与 `ioi/ex_ioi3.ans`。 【样例 4】 见选手目录下的 `ioi/ex_ioi4.in` 与 `ioi/ex_ioi4.ans`。 【数据范围】 对于所有的数据，字符串的长度 $n$ 满足 $3 \le n \le 5 \times 10^3$，且字符串中仅包含大写英文字母 `I` 和 `O`。 ::cute-table{tuack} | 测试点 | $n \le$ | 特殊性质 | |:------:|:-------------:|:--------------:| | $1$ | $1000$ | 字符全部为 `I` | | $2$ | $1000$ | 字符全部为 `O` | | $3\sim 13$ | $200$ | 无 | | $14\sim 20$ | $5 \times 10^3$ | 无 |