B-集邮比赛 2_JOI2016-Final比赛真题

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

本题译自 JOI 2016 Final T2「スタンプラリー 2」

至于 1 在哪儿……「スタンプラリー」这个标题曾出现在 JOI 2013/2014 春训营中，PoPoQQQ 大佬的译文戳这儿

JOI商店街有N家商店，这些商店从入口到出口依次编为 $1,2, \ldots,N$ 号。商店街是单向通道，只能从入口进去，向出口走。
为了振兴小镇，小镇将要举行集邮比赛。在集邮比赛上，每家商店都会准备 $\texttt{J,O,I}$ 三种邮票中的一种，在该商店中购物的顾客即可获得一张邮票。
在比赛中，参赛选手从入口进入商业街后，需要依次进入三家商店。每位选手在入口处会得知他需要依次进入哪三家商店。保证这三家商店依次提供邮票 $\texttt{J}$ ，邮票 $\texttt{O}$ 和邮票 $\texttt{I}$ 。选手到出口时凭赛时收集的这三张邮票领取购物券。
这N家商店已经决定了自己要准备哪种邮票。不过，在赛前，我们决定在商业街上新增一家店铺。这家店开张的地点可在店铺i和店铺i+1 $(1 \leqslant i \leqslant N-1)$ 之间，或者是入口与店铺1之间，亦或是店铺N与出口之间。这家新建的店铺也会参赛，并准备 $\texttt{J,O,I}$ 三种邮票中的一种。
选手获得礼品券的方式越多，邮票拉力赛就越热烈。如果两名选手进入的店铺不完全相同（比如三者都不同，或是两者相同剩下一家不同），那么这两名选手获得购物劵的方式不同。
我们想通过合理安排新店铺的开张地点，使得选手获得购物券的方式尽可能多。求在理想安排下，选手最多有多少种获得购物劵的方式。

输入描述:

第一行有一个整数N。
第二行有一个仅由三种字符组成的字符串，字符串长度为N。字符串左数第i个字符表示商店i提供哪种邮票。

输出描述:

输出一个整数，表示在理想安排下，选手最多有多少种获得购物券的方式。
保证答案在范围内。

示例1

输入

复制

5
JOIOI

输出

复制

说明

一种理想安排是新商店设置在商店1与商店2之间，该商店准备邮票。此时从入口走到出口，商店提供的邮票依次为。此时，有6种获得购物券的方式：
到商店1,3,4；
到商店1,3,6；
到商店1,5,6；
到商店2,3,4；
到商店2,3,6；
到商店2,5,6。

示例2

输入

复制

7
JJJOIII

输出

复制

示例3

输入

复制

4
OIIJ

输出

复制

说明

新商店设置在商店街入口与商店  之间，该商店准备邮票  。

备注:

对于的数据，。
对于的数据，。
对于所有数据，。

CC-BY-SA，感谢LOJ分享，译文来自https://loj.ac/problem/2343