配点: 100 点
JOIOI塔是什么?1 这是一种由人们玩的使用磁盘的游戏。
这个游戏是
这是通过使用多个磁盘来完成的,磁盘上写有字母J,O,I 之一。这些圆盘具有不同的直径,在游戏开始时,这些圆盘按照最大直径的顺序从下到上堆叠。您想使用这些圆盘来创建尽可能多的迷你 JOIOI 塔。什么是迷你JOIOI塔?
它由 3 磁盘组成,按直径从最小到最小的顺序读取。 JOI 或
它可以读作 IOI 。但同一个盘 2 不能多次使用。

課題
写在准备好的圆盘上的字母按照长度顺序排列,从圆盘的最小直径开始。 N 字符串 它被给出为 S 。编写一个程序来查找使用这些磁盘可以制作的迷你 JOIOI 塔的最大数量。
制限
| 1 \leqq N \leqq 1\,000\,000 | 文字列 S长度 |
入力
从标准输入读取以下数据。
- 第一行是一个整数 写入 N 。 表示N 是一个字符串 表示 S 的长度。
- 第二行是一个字符串 S 。 表示
出力
表示可以创建的迷你 JOIOI 塔的最大数量的整数被发送到标准输出。 输出为 1 行。
採点基準
评分数据中,分配的分数 10 对于%,N \leqq 15 很满意。
评分数据中,分配的分数 30 对于%,N \leqq 50 很满意。
评分数据中,分配的分数 50 对于%,N \leqq 3\,000 很满意。
入力例 1
6 JOIIOI
出力例 1
2
JOIIOI 为 JOI 和 IOI 分别 1 可以创建的迷你JOIOI塔是 2 这是一个。
入力例 2
5 JOIOI
出力例 2
1
作为子序列
包含 JOI 和 IOI ,但字符 2 不能多次使用,因此不能同时取出。
入力例 3
6 JOIOII
出力例 3
2
此输入/输出示例对应于问题文本中的示例。
入力例 4
15 JJOIIOOJOJIOIIO
出力例 4
4