Problem Description

The Tower of JOIOI is a game played with disks labeled with one of the letters J, O, or I. The disks have different diameters, and at the start of the game, they are stacked in order from largest to smallest diameter. Your goal is to create as many mini JOIOI towers as possible using these disks. A mini JOIOI tower consists of 3 disks that, when read from smallest to largest diameter, spell either JOI or IOI. Note that each disk can only be used once.

From JOIOII, 2 mini JOIOI towers can be made.

Input Format

Read the following data from standard input:

• The first line contains an integer $ N $, representing the length of the string $ S $.
• The second line contains the string $ S $.

Output Format

Output a single line with an integer representing the maximum number of mini JOIOI towers that can be created.

Sample Input and Output

Sample Input #1

6
JOIIOI

Sample Output #1

2

Sample Input #2

5
JOIOI

Sample Output #2

1

Sample Input #3

6
JOIOII

Sample Output #3

2

Sample Input #4

15
JJOIIOOJOJIOIIO

Sample Output #4

4

Notes/Hints

Task

Given a string $ S $ of length $ N $ where each character represents a disk labeled with J, O, or I in order from smallest to largest diameter, write a program to determine the maximum number of mini JOIOI towers that can be created using these disks.

Constraints

$1 \leq N \leq 1,000,000$

Grading Criteria

For 10% of the test cases, $N \leq 15$.

For 30% of the test cases, $N \leq 50$.

For 50% of the test cases, $N \leq 3,000$.

Sample Explanation 1

JOIIOI contains the subsequences JOI and IOI each once, so the maximum number of mini JOIOI towers that can be created is 2.

Sample Explanation 2

Although JOI and IOI are subsequences, they cannot be extracted simultaneously because no character can be used more than once.

Sample Explanation 3

This input/output example corresponds to the example given in the problem statement.

见题面 Input 部分

见题面 Output 部分