시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 44 30 30 69.767%

문제

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 が用意したスタンプの種類を表す.

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

  • 3 ≦ N ≦ 100 000.

출력

商品券をもらえるような店の選び方の数の最大値を標準出力に 1 行で出力せよ.

商品券をもらえるような店の選び方の数が 32 ビット符号付き整数の範囲に収まるとは限らないことに注意せよ.

예제 입력 1

5
JOIOI

예제 출력 1

6

예제 입력 2

7
JJJOIII

예제 출력 2

18

예제 입력 3

4
OIIJ

예제 출력 3

2