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 翻译