P11794 [JOI 2016 Final] 集邮比赛 2 / Collecting Stamps 2

给定一个长度为 $N$ 的仅包含字符 `J`、`O`、`I` 的字符串，现在你可以在该串的任意一个位置插入一个字符，求最多能有多少个子序列（不一定连续）为 `JOI`。

第一行一个整数 $n$，表示长度。 第二行为一个长度为 $n$ 的字符串。

一行，即添加后的子序列 `JOI` 的最大数量。

【数据范围与约定】 对于所有数据，均满足 $3 \le N \le 100000$。 1. Subtask $1$（$30$ pts）：$N \le 200$。 2. Subtask $2$（$20$ pts）：$N \le 3000$。 3. Subtask $3$（$50$ pts）：无特殊限制。