题目描述

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

5
JOIOI

输出 #1

6

输入输出样例 #2

输入 #2

7
JJJOIII

输出 #2

18

输入输出样例 #3

输入 #3

4
OIIJ

输出 #3

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）：无特殊限制。