题目描述

称由字符 I 和 O 构成的字符串为好串，当且仅当它能划分为三个非空连续部分：若干个 I、若干个 O、若干个 I。也就是说，好串的形式为 I...I O...O I...I，其中每部分的字符数至少为 $1$。

给定一个字符串 $S$，每次操作可以修改任意一个位置的字符（将 I 改为 O，或将 O 改为 I）。求至少需要多少次操作，才能将 $S$ 变为一个好串。

输入格式

一行，一个字符串 $S$，仅由大写字母 I 和 O 组成。

输出格式

输出一个整数，表示最少需要的修改次数。

样例

IIIOOOIOOII

1

样例解释

将第 $7$ 个字符 I 改为 O，得到 IIIOOOOOOII，可划分为 III、OOOOO、OII，满足好串条件。只需 $1$ 次修改，可以证明无法用 $0$ 次完成。

IOOIOOIOOOII

2

数据范围与提示

• $3 \le |S| \le 5 \times 10^3$
• $S$ 仅包含大写字母 I 和 O。