Problem Statement
Tower of JOIOI is a single-player game played using disks.
This game is played using several disks, each having one of the characters J, O, or I written on it. The disks have mutually different diameters, and at the start of the game, these disks are stacked from bottom to top in descending order of diameter. Using these disks, you want to make as many mini-JOIOI towers as possible. A mini-JOIOI tower consists of $3$ disks, and reads JOI or IOI when read in ascending order of disk diameter. However, the same disk cannot be used $2$ or more times.
Figure: $2$ mini-JOIOI towers can be made from JOIOII
Task
The characters written on the prepared disks are given as a string $S$ of length $N$ in ascending order of disk diameter. Write a program to find the maximum number of mini-JOIOI towers that can be made using these disks.
Limits
- $1 \le N \le 1000000$: The length of the string $S$.
Input
Read the following data from standard input.
- On the $1$-st line, an integer $N$ is written. $N$ represents the length of the string $S$.
- On the $2$-nd line, a string $S$ is written.
Output
Output to standard output on $1$ line an integer representing the maximum number of mini-JOIOI towers that can be made.
Subtasks
- For $10\%$ of the points in the grading data, $N \le 15$ is satisfied.
- For $30\%$ of the points in the grading data, $N \le 50$ is satisfied.
- For $50\%$ of the points in the grading data, $N \le 3000$ is satisfied.
Sample 1
Input
6 JOIIOI
Output
2
JOIIOI contains JOI and IOI as subsequences $1$ time each, so $2$ mini-JOIOI towers can be made.
Sample 2
Input
5 JOIOI
Output
1
Although it contains JOI and IOI as subsequences, a character cannot be used $2$ or more times, so they cannot be extracted simultaneously.
Sample 3
Input
6 JOIOII
Output
2
This sample corresponds to the example in the problem statement.
Sample 4
Input
15 JJOIIOOJOJIOIIO
Output
4