AT_joi2016ho_b スタンプラリー 2 (Collecting Stamps 2)

JOI 商店街沿着大街有 $N$ 家店铺，从入口到出口依次编号为 $1, 2, \ldots, N$。JOI 商店街是单向通行的，只能从入口向出口方向移动。 为了振兴商店街，JOI 商店街将举办一次集章活动。在这次集章活动中，每家店都准备了 `J`、`O`、`I` 三种印章中的一种，顾客在店内购物后可以在集章卡上盖章。参与活动的人恰好会进入 $3$ 家店。在入口处会发放有 $3$ 个栏位的集章卡，分别在第一次、第二次、第三次进入的店铺盖章。在出口处回收集章卡，如果盖章的顺序（按进入店铺的先后）恰好为 `J`、`O`、`I`，则可以在出口处获得商品券。如果盖章的种类或顺序不同，则无法获得商品券。 现在，$N$ 家店铺已经决定了各自准备哪种印章，但计划新开一家店，需要决定新店的位置和准备的印章。新店的位置可以选择在第 $i$ 家店和第 $i+1$ 家店之间（$1 \leq i \leq N-1$）、入口与第 $1$ 家店之间，或第 $N$ 家店与出口之间。新店的印章可以从 `J`、`O`、`I` 三种中任选其一。 商店街认为，能获得商品券的店铺选择方式越多，集章活动就越热闹。因此，请你求出新店的位置和印章种类都确定时，能获得商品券的店铺选择方式的最大值。

从标准输入读取以下内容。 - 第 $1$ 行包含一个整数 $N$，表示 JOI 商店街当前有 $N$ 家店铺。 - 第 $2$ 行包含一个仅由大写英文字母 `J`、`O`、`I` 组成的长度为 $N$ 的字符串 $S$。字符串 $S$ 的第 $i$ 个字符（$1 \leq i \leq N$）表示第 $i$ 家店准备的印章种类。

请输出能获得商品券的店铺选择方式的最大值，输出一行。 请注意，获得商品券的店铺选择方式的数量不一定能用 $32$ 位有符号整数表示。

## 任务 给定 JOI 商店街已有店铺准备的印章信息，请编写程序，求出新店的位置和印章种类都确定时，能获得商品券的店铺选择方式的最大值。 ## 限制 所有输入数据满足以下条件： - $3 \leq N \leq 100\,000$。 ## 子任务 ### 子任务 1 [30 分] - 满足 $N \leq 200$。 ### 子任务 2 [20 分] - 满足 $N \leq 3\,000$。 ### 子任务 3 [50 分] - 无额外限制。 ## 样例解释 1 在输入样例 $1$ 中，如果在第 $1$ 家店和第 $2$ 家店之间新开一家准备 `J` 印章的店，则从入口开始依次排列店铺的印章为 `JJOIOI`。此时，能获得商品券的店铺选择方式有以下 $6$ 种： - 进入第 $1, 3, 4$ 家店。 - 进入第 $1, 3, 6$ 家店。 - 进入第 $1, 5, 6$ 家店。 - 进入第 $2, 3, 4$ 家店。 - 进入第 $2, 3, 6$ 家店。 - 进入第 $2, 5, 6$ 家店。 在输入样例 $1$ 中，能获得商品券的店铺选择方式不会超过 $7$ 种。 ## 样例解释 2 - - - - - - ## 样例解释 3 在输入样例 $3$ 中，如果在入口与第 $1$ 家店之间新开一家准备 `J` 印章的店，能获得商品券的店铺选择方式数量达到最大。 由 ChatGPT 4.1 翻译