题目描述

本题译自 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$。
第二行有一个仅由 $\texttt{J,O,I}$ 三种字符组成的字符串，字符串长度为 $N$。字符串左数第 $i$ 个字符 $(1\leqslant i\leqslant N)$ 表示商店 $i$ 提供哪种邮票。

输出格式

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

5
JOIOI

6

7
JJJOIII

18

4
OIIJ

2

数据范围与提示

对于 $30\%$ 的数据，$N\leqslant 200$。
对于 $50\%$ 的数据，$N\leqslant 2000$。
对于所有数据，$1\leqslant N\leqslant 10^5$。