题目翻译

JOI商店街沿着主干道有N家商店，每家商店从入口到出口都有编号1,2,...,N。JOI商店街是单行道，只能从入口向出口方向移动。

为了振兴城市，决定在JOI商店街举办集章活动。在这个活动中，每家商店准备了J、O、I三种类型的章，并且在顾客购物时可以在顾客的集章卡上盖章。参加集章活动的顾客需要进入恰好三家商店。在商店街的入口处发放一张集章卡，其中有三个空格，分别填入第一次进入的商店、第二次进入的商店和第三次进入的商店的章。在商店街的出口处收回集章卡，如果盖章的类型和顺序依次为J、O、I，则可以获得礼券奖励。如果盖章的类型和顺序不同，则无法获得礼券奖励。

已经确定了所有N家商店的章的类型，现在要决定新增加一家店时该店的位置以及该店准备的章的类型。新店可以选择位置为商店i和商店i+1之间（1≤i≤N-1），入口和商店1之间，以及商店N和出口之间的任意位置。此外，新店的章有三种选择：J、O、I。

商店街认为，选择能够获得礼券的店铺方式的数量越多，集章活动的热度就会越高。因此，希望计算出当确定新增加一家店的位置以及该店准备的章的类型时，能够获得礼券的店铺方式数量的最大值。

任务

给定JOI商店街已经准备的章的信息，请编写一个程序，计算在确定新增加一家店的位置和该店准备的章的类型时，能够获得礼券的店铺方式数量的最大值。

输入

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

• 第1行包含一个整数N，表示JOI商店街当前共有N家商店。
• 第2行包含一个由N个大写英文字母J、O、I组成的字符串S。字符串S的第i个字符（1≤i≤N）表示第i家商店准备的章的类型。

输出

将能够获得礼券的店铺方式数量的最大值输出到标准输出中。

注意：获得礼券的店铺方式数量可能超出32位有符号整数的范围。

限制条件

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

• 3≤N≤100,000。

示例

输入示例1

5
JOIOI

输出示例1

6

在示例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中，当在入口和商店1之间开设一家新店，准备J类型的章时，可以获得礼券的店铺方式的数量最大。