题目描述

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

输入格式

第一行一个整数 $n$，表示长度。

第二行为一个长度为 $n$ 的字符串。

输出格式

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

5
JOIOI

6

7
JJJOIII

18

4
OIIJ

2

提示

【数据范围与约定】

对于所有数据，均满足 $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）：无特殊限制。