题目描述

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

这个游戏使用若干个圆盘进行，每个圆盘上都写有 J、O、I 中的某一个字符。各圆盘的直径互不相同，在游戏开始时，这些圆盘按直径从大到小的顺序从下往上堆叠在一起。你想要使用这些圆盘，制作出尽可能多的迷你 JOIOI 之塔。一座迷你 JOIOI 之塔由 $3$ 个圆盘组成，按圆盘直径从小到大的顺序读出时为 JOI 或 IOI。但是，同一个圆盘不能被使用 $2$ 次或以上。

图：从 JOIOII 可以制作出 $2$ 座迷你 JOIOI 之塔

任务

准备好的圆盘上所写的字符按圆盘直径从小到大的顺序作为长度为 $N$ 的字符串 $S$ 给出。请编写一个程序，求出使用这些圆盘能够制作的迷你 JOIOI 之塔数量的最大值。

限制

• $1 \le N \le 1000000$：字符串 $S$ 的长度。

输入格式

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

• 第 $1$ 行写有一个整数 $N$。$N$ 表示字符串 $S$ 的长度。
• 第 $2$ 行写有一个字符串 $S$。

输出格式

向标准输出输出 $1$ 行，表示能够制作的迷你 JOIOI 之塔数量的最大值的整数。

子任务

• 在占总分 $10\%$ 的评测数据中，满足 $N \le 15$。
• 在占总分 $30\%$ 的评测数据中，满足 $N \le 50$。
• 在占总分 $50\%$ 的评测数据中，满足 $N \le 3000$。

样例 1

输入

6
JOIIOI

输出

2

JOIIOI 各自包含 $1$ 个 JOI 和 IOI 作为子序列，因此可以制作出 $2$ 座迷你 JOIOI 之塔。

样例 2

输入

5
JOIOI

输出

1

虽然包含 JOI 和 IOI 作为子序列，但由于同一个字符不能被使用 $2$ 次或以上，因此无法同时取出。

样例 3

输入

6
JOIOII

输出

2

该样例对应题目描述中的例子。

样例 4

输入

15
JJOIIOOJOJIOIIO

输出

4