#2343. 「JOI 2016 Final」集邮比赛 2

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

本题译自 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} 范围内。

样例

输入样例 1

5
JOIOI

输出样例 1

6

样例解释 1

一种理想安排是新商店设置在商店 1 与商店 2 之间,该商店准备邮票 \texttt{J} 。此时从入口走到出口,商店提供的邮票依次为 \texttt{JJOIOI} 。此时,有 6 种获得购物券的方式:

  • 到商店 1,3,4
  • 到商店 1,3,6
  • 到商店 1,5,6
  • 到商店 2,3,4
  • 到商店 2,3,6
  • 到商店 2,5,6

输入样例 2

7
JJJOIII

输出样例 2

18

输入样例 3

4
OIIJ

输出样例 3

2

样例解释 3

新商店设置在商店街入口与商店 1 之间,该商店准备邮票 \texttt{J}

数据范围与提示

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