JOI 商店街には大通りに沿って N 個の店があり，JOI 商店街の入口から出口に向かってそれぞれ 1, 2, \ldots, N の番号が付けられている．JOI 商店街は一方通行で，入口から出口方向へしか移動することはできない．

まちおこしのため，JOI 商店街でスタンプラリーを行うことになった．このスタンプラリーでは，それぞれの店は J，O，I のいずれかのスタンプを用意し，店で買い物をした人はスタンプカードにスタンプを押してもらう．スタンプラリーに参加する人はちょうど 3 つの店に入る．商店街の入口では 3 つの欄のあるスタンプカードを配り，1 回目に入った店，2 回目に入った店，3 回目に入った店のスタンプを押してもらう．商店街の出口でスタンプカードを回収し，押されたスタンプが先に入った店のものから順に J，O，I になっているとき，出口で商品券がもらえるキャンペーンを実施することになった．押されたスタンプの種類や順番が異なるときは商品券はもらえない．

すでに N 個のすべての店はどのスタンプを用意するか決めたが，新たに 1 つの店を JOI 商店街に出すことになり，新しく出店する場所と，その店が用意するスタンプを決めることになった．新しい店を出す場所は，店 i と店 i + 1 の間 (1 \leqq i \leqq N - 1)，入口と店 1 の間，店 N と出口の間のいずれかから決める．また，新しい店のスタンプは J，O，I の 3 通りから決める．

商品券をもらえるような店の選び方の数が大きいほど，スタンプラリーが盛り上がると商店街は考えた．そこで，新しく出す店の場所と用意するスタンプを決めたときの，上記の店の選び方の数の最大値を求めたい．

課題

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

制限

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

• 3 \leqq N \leqq 100\,000．

小課題

小課題 1 [30 点]

• N \leqq 200 を満たす．

小課題 2 [20 点]

• N \leqq 3\,000 を満たす．

小課題 3 [50 点]

追加の制限はない．

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