002 - スタンプラリー ２ (Collecting Stamps 2)

問題

　JOI 商店街には大通りに沿って N 個の店があり，JOI 商店街の入口から出口に向かってそれぞれ 1, 2, ..., N の番号が付けられている．JOI 商店街は一方通行で，入口から出口方向へしか移動することはできない．
　まちおこしのため，JOI 商店街でスタンプラリーを行うことになった．このスタンプラリーでは，それぞれの店は J，O，I のいずれかのスタンプを用意し，店で買い物をした人はスタンプカードにスタンプを押してもらう．スタンプラリーに参加する人はちょうど 3 つの店に入る．商店街の入口では 3 つの欄のあるスタンプカードを配り，1 回目に入った店，2 回目に入った店，3 回目に入った店のスタンプを押してもらう．商店街の出口でスタンプカードを回収し，押されたスタンプが先に入った店のものから順に J，O，I になっているとき，出口で商品券がもらえるキャンペーンを実施することになった．押されたスタンプの種類や順番が異なるときは商品券はもらえない．
　すでに N 個のすべての店はどのスタンプを用意するか決めたが，新たに 1 つの店を JOI 商店街に出すことになり，新しく出店する場所と，その店が用意するスタンプを決めることになった．新しい店を出す場所は，店 i と店 i + 1 の間 (1 ≤ i ≤ N - 1)，入口と店 1 の間，店 N と出口の間のいずれかから決める．また，新しい店のスタンプは J，O，I の 3 通りから決める．
　商品券をもらえるような店の選び方の数が大きいほど，スタンプラリーが盛り上がると商店街は考えた．そこで，新しく出す店の場所と用意するスタンプを決めたときの，上記の店の選び方の数の最大値を求めたい．

課題

　JOI 商店街のすでにある店が用意したスタンプの情報が与えられたとき，新しく出す店の場所と用意するスタンプを決めたときの，商品券をもらえるような店の選び方の数の最大値を求めるプログラムを作成せよ．

入力

　標準入力から以下の入力を読み込め．

• 1 行目には，1 つの整数 N が書かれている．これは，JOI 商店街には現在 N 個の店があることを意味する．
• 2 行目には，N 文字の半角英大文字 J, O, I のみからなる文字列 S が書かれている．文字列 S の左から i 文字目 (1 ≤ i ≤ N) は，店 i が用意したスタンプの種類を表す．

出力

　商品券をもらえるような店の選び方の数の最大値を標準出力に 1 行で出力せよ．
　商品券をもらえるような店の選び方の数が 32 ビット符号付き整数の範囲に収まるとは限らないことに注意せよ．

制限

　すべての入力データは以下の条件を満たす.

• 3 ≤ N ≤ 100 000．

小課題

小課題 1 [30 点]

• N ≤ 200 を満たす．

小課題 2 [30 点]

• N ≤ 3 000 を満たす．

小課題 3 [30 点]

　追加の制限はない．

入出力例

入力例 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 を用意する新しい店を出したとき，商品券をもらえるような店の選び方の数が最大となる．