P15809 [JOI 2013 Final] JOIOI 塔 / Tower of JOIOI

**JOIOI 之塔** 是一款使用圆盘的单人游戏。 这个游戏使用一些写有字符 **J**, **O**, **I** 之一的圆盘进行。圆盘的直径互不相同，游戏开始时，这些圆盘按照直径从大到小的顺序，从下到上堆叠在一起。你想用这些圆盘制作尽可能多的迷你 **JOIOI 之塔**。一个迷你 **JOIOI 之塔** 由 3 个圆盘组成，从直径最小的圆盘开始读，可以读作 **JOI** 或 **IOI**。但是，同一个圆盘不能使用两次或以上。 :::align{center}  图：从 **JOIOII** 可以制作出 2 个迷你 **JOIOI 之塔** ::: ### 任务 给定一个长度为 $N$ 的字符串 $S$，它表示所准备的圆盘上写的字符，按照圆盘直径从小到大的顺序排列。编写一个程序，求出使用这些圆盘可以制作的迷你 **JOIOI 之塔** 的最大数量。

从标准输入读取以下数据。 - 第一行包含一个整数 $N$。$N$ 表示字符串 $S$ 的长度。 - 第二行包含字符串 $S$。

向标准输出输出一行，包含一个整数，表示可以制作的迷你 **JOIOI 之塔** 的最大数量。

### 样例解释 1. JOIIOI 分别包含 **JOI** 和 **IOI** 各一次作为子序列，可以制作的迷你 **JOIOI 之塔** 数量为 2。 2. 虽然包含 **JOI** 和 **IOI** 作为子序列，但由于不能重复使用字符，无法同时取出它们。 3. 此样例对应于题目描述中的例子。 ### 限制 $1 \leq N \leq 1\,000\,000$　字符串 $S$ 的长度 ### 评分标准 在评分数据中，占分值 10% 的部分满足 $N \leq 15$。 在评分数据中，占分值 30% 的部分满足 $N \leq 50$。 在评分数据中，占分值 50% 的部分满足 $N \leq 3000$。 --- 翻译由 DeepSeek V3.2 完成