Problem Description

There are $ N $ shops along the main street in JOI Shopping District, numbered $1, 2, \ldots, N$ from the entrance to the exit. The shopping district is one-way, and movement is only allowed from the entrance towards the exit.

For revitalization, a stamp rally event is being held in JOI Shopping District. Each shop prepares one of the stamps J, O, I, and customers who shop at a store can get their stamp card stamped. Participants in the stamp rally visit exactly $ 3 $ shops. At the entrance, a stamp card with $ 3 $ slots is distributed, and the stamps from the first, second, and third shops visited are collected. At the exit, a campaign is held where a gift voucher is awarded if the stamps on the card are in the order J, O, I from the first visited shop to the last. If the types or order of the stamps are different, no gift voucher is awarded.

All $ N $ shops have already decided which stamp to prepare, but a new shop is to be opened in the JOI Shopping District, and the location of this new shop and the stamp it will prepare need to be decided. The new shop can be located between shop $ i $ and shop $ i + 1 $ ($1 \leq i \leq N - 1$), between the entrance and shop $ 1 $, or between shop $ N $ and the exit. The new shop's stamp can be one of J, O, I.

The shopping district believes that the more ways there are to choose shops that qualify for the gift voucher, the more successful the stamp rally will be. Therefore, they want to determine the maximum number of ways to choose shops that qualify for the gift voucher when the location and stamp of the new shop are decided.

Input Format

Read the following input from standard input:

• The first line contains a single integer $ N $, which indicates the current number of shops in JOI Shopping District.
• The second line contains a string $ S $ of $ N $ uppercase letters J, O, I, where the $ i $-th character ($1 \leq i \leq N$) represents the type of stamp prepared by shop $ i $.

Output Format

Output the maximum number of ways to choose shops that qualify for the gift voucher to standard output in one line.

Note that the number of ways to choose shops that qualify for the gift voucher may not fit within a 32-bit signed integer.

Sample Input and Output

Sample Input #1

5
JOIOI

Sample Output #1

6

Sample Input #2

7
JJJOIII

Sample Output #2

18

Sample Input #3

4
OIIJ

Sample Output #3

2

Notes/Hints

Task

Given the information about the stamps prepared by the existing shops in JOI Shopping District, create a program that determines the maximum number of ways to choose shops that qualify for the gift voucher when the location and stamp of the new shop are decided.

Constraints

All input data satisfies the following conditions:

• $3 \leq N \leq 100,000$.

Subtasks

Subtask 1 [30 points]

• $N \leq 200$.

Subtask 2 [20 points]

• $N \leq 3,000$.

Subtask 3 [50 points]

No additional constraints.

Sample Explanation 1

In Sample Input #1, when a new shop with stamp J is opened between shop $ 1 $ and shop $ 2 $, the stamps from the shops arranged from the entrance are JJOIOI. In this case, there are $ 6 $ ways to choose shops that qualify for the gift voucher:

• Visit shops $ 1, 3, 4 $.
• Visit shops $ 1, 3, 6 $.
• Visit shops $ 1, 5, 6 $.
• Visit shops $ 2, 3, 4 $.
• Visit shops $ 2, 3, 6 $.
• Visit shops $ 2, 5, 6 $.

In Sample Input #1, there are no more than $ 7 $ ways to choose shops that qualify for the gift voucher.

Sample Explanation 2

Sample Explanation 3

In Sample Input #3, the maximum number of ways to choose shops that qualify for the gift voucher is achieved when a new shop with stamp J is opened between the entrance and shop $ 1 $.

见题面 Input 部分

见题面 Output 部分