说明

JOIOI 之塔 是一款使用圆盘的单人游戏。

这个游戏使用一些写有字符 J, O, I 之一的圆盘进行。圆盘的直径互不相同，游戏开始时，这些圆盘按照直径从大到小的顺序，从下到上堆叠在一起。你想用这些圆盘制作尽可能多的迷你 JOIOI 之塔。一个迷你 JOIOI 之塔 由 3 个圆盘组成，从直径最小的圆盘开始读，可以读作 JOI 或 IOI。但是，同一个圆盘不能使用两次或以上。

:::align{center}

图：从 JOIOII 可以制作出 2 个迷你 JOIOI 之塔 :::

任务

给定一个长度为 $N$ 的字符串 $S$，它表示所准备的圆盘上写的字符，按照圆盘直径从小到大的顺序排列。编写一个程序，求出使用这些圆盘可以制作的迷你 JOIOI 之塔 的最大数量。

输入格式

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

• 第一行包含一个整数 $N$。$N$ 表示字符串 $S$ 的长度。
• 第二行包含字符串 $S$。

输出格式

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

6
JOIIOI

2

5
JOIOI

1

6
JOIOII

2

15
JJOIIOOJOJIOIIO

4

提示

样例解释

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 完成