Collecting Stamps 2

Interview

Time limit2sMemory limit256 MB

Summary

Insert one J, O, or I stamp at any position to maximize the number of triples that read J, O, I in order.

Level: Medium4 of 10
Topics: Prefix sum, Combinatorics
Solved: No attempts yet

Problem

The JOI shopping street has $N$ shops along the main road, numbered $1, 2, \dots, N$ from the entrance toward the exit. The street is one way, so you move only from the entrance toward the exit.

To bring in visitors, the street holds a stamp rally. Each shop prepares one stamp out of J, O and I, and anyone who buys something at a shop gets that shop's stamp on a stamp card. A participant enters exactly three shops. At the entrance every participant receives a card with three boxes, and the stamps of the first, the second and the third shop visited go into the boxes in that order. The cards are collected at the exit, and a participant whose stamps read J, O, I in visiting order receives a gift voucher. A different set of stamps or a different order gets nothing.

The street is one way, so the three chosen shops are always visited from the smallest number upward. A choice that earns a voucher is therefore a triple of shops $i < j < k$ whose stamps are J, O and I in that order.

All $N$ existing shops have already fixed their stamps, but one more shop will open on the street, and both its position and its stamp have to be decided. The new shop goes between shop $i$ and shop $i+1$ for some $1 \le i \le N-1$ , or between the entrance and shop $1$ , or between shop $N$ and the exit. Its stamp is one of J, O and I. A participant may enter the new shop too.

The street believes the rally does better when more choices of shops earn a voucher. Find the maximum, over every position and every stamp for the new shop, of the number of choices that earn a voucher.

Input

Read the following from standard input.

The first line has one integer $N$ . The JOI shopping street currently has $N$ shops.
The second line has a string $S$ of length $N$ made only of the uppercase letters J, O and I. The $i$ -th character of $S$ from the left ( $1 \le i \le N$ ) is the stamp that shop $i$ prepared.

Output

Print on one line of standard output the maximum number of shop choices that earn a voucher.

The number does not always fit in a 32-bit signed integer.

Constraints

$3 \le N \le 100000$
$S$ is a string of length $N$ made only of J, O and I.

Examples3

Example 1
Input
```
5
JOIOI
```
Expected output
```
6
```
Example 2
Input
```
7
JJJOIII
```
Expected output
```
18
```
Example 3
Input
```
4
OIIJ
```
Expected output
```
2
```