JOIOI Tower

Time limit1sMemory limit128 MB

Summary

Given a string of J, O, I disks by increasing radius, find the maximum number of disjoint triples spelling JOI or IOI.

Level: Medium5 of 10
Topics: Greedy, Array, String
Solved: No attempts yet

Problem

JOIOI Tower is a solitaire game played by stacking disks.

The game uses disks, each labeled with one of the letters J, O, or I. All disks have distinct radii, and they start stacked so that the disk with the largest radius is at the bottom and the radii decrease going up.

Using these disks, you want to build as many mini JOIOI towers as possible. A mini JOIOI tower consists of 3 disks, and reading their letters from the smallest radius to the largest must spell JOI or IOI. Each disk may belong to at most one tower. The three disks of a tower need not be adjacent in the original stack.

Given the letters written on the disks in order of increasing radius, find the maximum number of mini JOIOI towers you can build.

Input

The first line contains the number of disks $N$ . $(1 \le N \le 1\,000\,000)$

The second line contains the letters on the disks, in order of increasing radius, with no spaces. Each letter is one of J, O, or I.

Output

Print the maximum number of mini JOIOI towers that can be built.

Examples4

Example 1
Input
```
6
JOIIOI
```
Expected output
```
2
```
Example 2
Input
```
5
JOIOI
```
Expected output
```
1
```
Example 3
Input
```
6
JOIOII
```
Expected output
```
2
```
Example 4
Input
```
15
JJOIIOOJOJIOIIO
```
Expected output
```
4
```