该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

IOI串(ioi)

【题目描述】

小明对字符串"IOI"怀有特殊的感情，他定义一种由大写英文字母 'I' 和 'O' 构成的字符串为“好串”，当且仅当它可以被划分为三个非空部分，依次为：

• 第一部分：连续若干个 'I'
• 第二部分：连续若干个 'O'
• 第三部分：连续若干个 'I'

例如： "IIIOOIII" 是一个好串，"IOI"也是一个好串； "OIOI"，"IIO" 都不是好串。

现在，小明有一个长度为n的字符串S，且S仅包含字符 'I' 和 'O'。 他可以进行任意次修改操作，每一次操作可将字符串中某一个位置的字符替换成另一个字符（即把 'I' 改为 'O'，或把 'O' 改为 'I'）。

例如： 当S="IIIOOOIOII"时，根据上述定义，S不是一个“好串”，但小明可以有多种方法通过修改操作把S变为“好串”：

• 方法1：把第7个字符 'I' 改为 'O'，经过1次操作得到 "IIIOOOOII"；
• 方法2：分别把第8个和第9个字符 'O' 改为 'I'，经过2次操作得到 "IIIOOOIIIII"。

你的任务：至少经过1次修改操作才能把上面的字符串S变为“好串”。 请你根据小明的字符串S，计算至少需要进行多少次修改操作，才能将字符串S变为一个“好串”。如果S已经是一个“好串”，输出0。

【输入格式】

从文件 ioi.in 中读入数据。 一行，仅由 'I' 和 'O' 两种字符组成的字符串S。

【输出格式】

输出到文件 ioi.out 中。 一行，包含一个整数，表示把字符串S修改为“好串”需要的最少的修改次数。

IOI串(ioi) - 样例与数据范围

【样例 1 输入】

IIIOOOIOII

【样例 1 输出】

1

【样例 2 输入】

IOOIOOIOOOII

【样例 2 输出】

2

【样例 3】

见选手目录下的 ioi/ex_ioi3.in 与 ioi/ex_ioi3.ans。

【样例 4】

见选手目录下的 ioi/ex_ioi4.in 与 ioi/ex_ioi4.ans。

【数据范围】

对于所有的数据，字符串的长度 n 满足 $3 \leq n \leq 5 \times 10^3$，且字符串中仅包含大写英文字母'I'和'O'。