JOIOI の塔

JOIOI の塔是一款使用一个人玩的圆盘游戏。

此游戏使用了标有 J，O，I 中任意字符的几个圆盘进行。这些圆盘的直径各不相同，并且在游戏开始时，这些圆盘从下往上按照直径从大到小的顺序堆叠起来。您需要利用这些圆盘尽可能多地构建小 JOIOI 的塔。小 JOIOI 的塔由3个圆盘组成，圆盘的直径从小到大依次读取可以读出 JOI 或者 IOI 的塔。但是，请注意，不能多次使用同一个圆盘。

从 "JOIOII" 可以构建两个小 JOIOI 的塔。

任务

给定一组标有字符的圆盘，并将它们按照直径从小到大的顺序组成长度为 $N$ 的字符串 $S$，请编写一个程序来确定可以构建的小 JOIOI 塔的最大数量。

限制

$1 \leq N \leq 1,000,000$

字符串 $S$ 的长度

---

输入

从标准输入读取以下数据：

• 第1行包含整数 $N$。$N$ 表示字符串 $S$ 的长度。
• 第2行包含字符串 $S$。

输出

在标准输出中以一行表示能够构建的小 JOIOI 塔的最大数量。

评分标准

在评分的数据中，对于10%的数据，满足 $N \leq 15$。

在评分的数据中，对于30%的数据，满足 $N \leq 50$。

在评分的数据中，对于50%的数据，满足 $N \leq 3,000$。

---

示例 1

6
JOIIOI

输出示例 1

2

"JOIIOI" 包含了一个 "JOI" 和一个 "IOI" 作为子序列，并且可以构建的小 JOIOI 塔的数量为2个。

---

示例 2

5
JOIOI

输出示例 2

1

虽然包含 "JOI" 和 "IOI" 作为子序列，但由于不允许使用同一个圆盘多次，所以无法同时取出。

---

示例 3

6
JOIOII

输出示例 3

2

这个示例与问题描述中的示例相对应。

---

示例 4

15
JJOIIOOJOJIOIIO

输出示例 4

4