IOI String

Interview

Time limit2sMemory limit1024 MB

Summary

Given an odd-length uppercase string S, find the minimum number of single-character changes needed to make it an alternating I/O string starting with I.

Level: Easy2 of 10
Topics: String, Implementation, Brute force, Greedy
Solved: No attempts yet

Problem

You are given a string S of odd length. Each character of S is an uppercase English letter.

An IOI string is a string that satisfies all of the following conditions.

Its length is odd.
Each character is I or O, and these characters alternate.
The first character is I.

For example, I, IOI, and IOIOIOI are IOI strings, but JOI, IIOOII, and OIOIO are not.

You may repeat the following operation zero or more times.

Choose one character of S and change it to any uppercase English letter.

Find the minimum number of operations needed to turn S into an IOI string.

Input

The input is given from standard input in the following format.

N
S

Output

Print the minimum number of operations needed to turn the string S into an IOI string.

Constraints

1 ≤ N ≤ 99.
N is odd.
S is a string of length N.
Each character of S is an uppercase English letter.

Examples4

Example 1
Input
```
5
JJOOI
```
Expected output
```
3
```
Example 2
Input
```
7
IOIOIOI
```
Expected output
```
0
```
Example 3
Input
```
7
BEAVERS
```
Expected output
```
7
```
Example 4
Input
```
5
OIOIO
```
Expected output
```
5
```