JOI 商店街的大街沿线有 $N$ 家店，从入口到出口依次编号为 $1, 2, \dots, N$。JOI 商店街是单行道，只能从入口向出口方向移动。

为了振兴城镇，JOI 商店街决定举办集章活动。在这次活动中，每家店都会准备 J、O、I 三种印章中的一种，在店里购物的人可以获得相应的印章。参加集章活动的人需要进入恰好 3 家店。商店街在入口处分发带有 3 个栏位的集章卡，分别盖上第 1 次进入的店、第 2 次进入的店和第 3 次进入的店的印章。如果在商店街出口处回收集章卡时，盖上的印章按进入店的先后顺序依次为 J、O、I，则可以在出口处获得礼券。如果印章的种类或顺序不同，则无法获得礼券。

虽然 $N$ 家店已经决定了各自准备的印章，但现在决定在 JOI 商店街新开一家店，并需要确定新店的位置以及该店准备的印章。新店的位置可以选在店 $i$ 和店 $i+1$ 之间 ($1 \le i \le N-1$)、入口和店 1 之间，或者店 $N$ 和出口之间。此外，新店的印章可以从 J、O、I 三种中选择。

商店街认为，能够获得礼券的选店方式越多，集章活动就越热闹。因此，请计算在确定了新店的位置和准备的印章后，能够获得礼券的选店方式的最大数量。

题目描述

给定 JOI 商店街现有店铺准备的印章信息，请编写一个程序，计算在确定了新店的位置和准备的印章后，能够获得礼券的选店方式的最大数量。

输入格式

从标准输入读取以下内容：

• 第 1 行包含一个整数 $N$，表示 JOI 商店街目前有 $N$ 家店。
• 第 2 行包含一个长度为 $N$ 的字符串 $S$，仅由大写英文字母 J、O、I 组成。字符串 $S$ 的第 $i$ 个字符 ($1 \le i \le N$) 表示店 $i$ 准备的印章种类。

输出格式

将能够获得礼券的选店方式的最大数量输出到标准输出，占一行。

注意，能够获得礼券的选店方式的数量可能超过 32 位有符号整数的范围。

数据范围

所有输入数据满足以下条件：

• $3 \le N \le 100\,000$

子任务

1. (30 分) 满足 $N \le 200$。
2. (20 分) 满足 $N \le 3\,000$。
3. (50 分) 没有额外限制。

样例

样例输入 1

5
JOIOI

样例输出 1

6

说明 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

7
JJJOIII

样例输出 2

18

样例输入 3

4
OIIJ

样例输出 3

2

说明 3

在样例 3 中，在入口和店 1 之间开设一家准备 J 印章的新店时，能够获得礼券的选店方式数量达到最大。