题目描述

小明对字符串 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$ 修改为“好串”需要的最少的修改次数。

IIIOOOIOOII

1

IOOIOOIOOOII

2

说明与数据范围

【样例 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。

来源与本地评测说明

来源：洛谷 B4426。题面按来源整理，源题号保留。

本地测试数据自行构造，经过独立 Python 基准、边界对拍及 Linux C++17 沙箱核验，并非洛谷原版完整评测数据。本地训练分值归一为100分。原题提及但未提供的选手目录附件样例不在本地附件中；本页列出的输入输出样例完整保留。