4355: 「JOI 2016 Final」集邮比赛 2

**本题译自 [JOI 2016 Final](https://www.ioi-jp.org/joi/2015/2016-ho/index.html) T2「[スタンプラリー 2](https://www.ioi-jp.org/joi/2015/2016-ho/2016-ho.pdf)」** >至于 1 在哪儿……「スタンプラリー」这个标题曾出现在 JOI 2013/2014 春训营中，PoPoQQQ 大佬的译文戳[这儿](http://www.lydsy.com/JudgeOnline/problem.php?id=4244) 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$。 第二行有一个仅由 $\texttt{J,O,I}$ 三种字符组成的字符串，字符串长度为 $N$。字符串左数第 $i$ 个字符 $(1\leqslant i\leqslant N)$ 表示商店 $i$ 提供哪种邮票。

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

5
JOIOI

6