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

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

题目描述

给定一个长度为 NN 的仅包含字符 JOI 的字符串,现在你可以在该串的任意一个位置插入一个字符,求最多能有多少个子序列(不一定连续)为 JOI

输入格式

第一行一个整数 nn,表示长度。

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

输出格式

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

5
JOIOI
6
7
JJJOIII
18
4
OIIJ
2

提示

【数据范围与约定】

对于所有数据,均满足 3N1000003 \le N \le 100000

  1. Subtask 113030 pts):N200N \le 200
  2. Subtask 222020 pts):N3000N \le 3000
  3. Subtask 335050 pts):无特殊限制。