시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 7 5 5 100.000%

문제

JOI 상점가에는 큰길을 따라 N 개의 가게가 있으며, JOI 상점가의 입구부터 출구 쪽으로 1, 2, ... N 번의 번호가 붙어 있습니다. JOI 상점가는 일방통행이며, 입구부터 출구 방향으로 이동이 가능합니다.

마을을 부흥식 키기 위해, JOI 상점가에서 스탬프랠리를 하게 되었습니다. 이 스탬프랠리는, 각각의 가게에 J, O, I의 스탬프를 준비하고, 가게에 물건을 산 사람의 스탬프 카드에 스탬프를 찍어줍니다. 스탬프랠리에 참가한 사람은 최소 3개의 가게에 들어가야 합니다. 상점가의 입구에는 3개의 란에서 스탬프 카드를 나눠주며, 첫 번째로 들어간 가게, 두 번째로 들어간 가게, 세 번째로 들어간 가게의 스탬프를 받습니다. 상점가의 출구에는 스탬프 카드를 회수하며, 스탬프를 받은 순서대로 J, O, I 가 되면, 이번 캠페인에서 준비한 상품권을 상품으로 받을 수 있습니다. 찍었던 순서가 J, O, I가 아닌 다른 순서가 되면 상품권은 받지 못 합니다.

이미 N 개의 가게에 어떤 스탬프를 준비할지 결정하였으나, 1가지 새로운 가게가 JOI 상점가에 들어올 경우, 가게를 여는 장소와 그 가게가 준비하는 스탬프를 정하게 되었습니다. 새롭게 내놓을 가게의 장소는, 가게 i와 가게 i+1 의 사이(1 ≦ i ≦ N − 1), 입구와 가게 1 의 사이, 가게 N 과 출구의 사이 중 하나를 결정하게 되었습니다. 그리고, 새로운 가게의 스탬프는 J, O, I의 3개 중 하나로 결정합니다.

상품권을 받을 수 있는 가게의 선택 방법의 수가 클수록, 스탬프랠리가 흥하자 상점가는 생각했습니다. 거기서, 새로운 가게의 장소를 준비와 준비하는 스탬프를 결정할 때, 상기의 가게에서 선택 방법을 최대치로 구하여야 합니다.

JOI 상점가는 이미 있는 가게가 준비한 정보가 주어졌을 때, 새로운 가게의 장소와 준비하는 스탬프를 결정할 때, 상품권을 받을 수 있는 상점가의 선택의 수를 최대치로 구하여야 합니다.

입력

표준 입력은 다음과 같이 입력합니다.

  • 1번째 행에는 1개의 정수 N을 씁니다. 정수 N은 JOI상점가에 현재 존재하는 N개의 가게를 의미합니다.
  • 2번째 행에는 J, O, I 만 들어가는 문자열 S를 씁니다. 문자열 S는 왼쪽으로 부터 i문자열(1 ≦ i ≦ N) 까지이며, 가게 i는 준비하는 스탬프의 종류 중 하나를 표현합니다.

전체적인 입력 조건은 다음과 같습니다.

  •  3 ≦ N ≦ 100 000.

출력

상품권을 받을 수 있는 경우의 수 중 최대치를 찾아서 1행에 출력하여 주십시오.

상품권을 받을 수 있는 가게의 선택 방법은 32비트의 부호의 정수 범위가 아닐 수도 있음에 주의하여 주십시오.

예제 입력

5
JOIOI

예제 출력

6

예제 입력 2

7
JJJOIII

예제 출력 2

18

예제 입력 3

4
OIIJ

예제 출력 3

2

힌트

출처

Olympiad > 일본정보올림피아드 > JOI 2016 2번

  • 문제를 번역한 사람: dlvmy