Descripción del problema

La Torre de JOIOI es un juego para $1$ jugador que utiliza discos.

Este juego se juega utilizando varios discos, cada uno de los cuales tiene escrito uno de los caracteres J, O o I. Los discos tienen diámetros mutuamente distintos y, al comienzo del juego, estos discos están apilados de abajo hacia arriba en orden descendente de diámetro. Usando estos discos, quieres construir tantas minitorres JOIOI como sea posible. Una minitorre JOIOI consta de $3$ discos y se lee JOI o IOI cuando se lee en orden ascendente de diámetro de los discos. Sin embargo, no se puede usar el mismo disco $2$ o más veces.

Figura: A partir de JOIOII se pueden construir $2$ minitorres JOIOI

Tarea

Los caracteres escritos en los discos preparados se dan como una cadena $S$ de longitud $N$ en orden ascendente de diámetro de los discos. Escribe un programa para encontrar el número máximo de minitorres JOIOI que se pueden construir usando estos discos.

Límites

• $1 \le N \le 1000000$: La longitud de la cadena $S$.

Entrada

Lee los siguientes datos desde la entrada estándar.

• En la $1$-ra línea está escrito un entero $N$. $N$ representa la longitud de la cadena $S$.
• En la $2$-da línea está escrita una cadena $S$.

Salida

Imprime en la salida estándar en $1$ línea un entero que represente el número máximo de minitorres JOIOI que se pueden construir.

Subtareas

• Para el $10\%$ de los puntos en los datos de evaluación, se cumple $N \le 15$.
• Para el $30\%$ de los puntos en los datos de evaluación, se cumple $N \le 50$.
• Para el $50\%$ de los puntos en los datos de evaluación, se cumple $N \le 3000$.

Ejemplo 1

Entrada

6
JOIIOI

Salida

2

JOIIOI contiene a JOI e IOI $1$ vez cada uno como subsecuencia, por lo que se pueden construir $2$ minitorres JOIOI.

Ejemplo 2

Entrada

5
JOIOI

Salida

1

Aunque contiene a JOI e IOI como subsecuencias, un carácter no se puede usar $2$ o más veces, por lo que no se pueden extraer simultáneamente.

Ejemplo 3

Entrada

6
JOIOII

Salida

2

Este ejemplo corresponde al ejemplo en la descripción del problema.

Ejemplo 4

Entrada

15
JJOIIOOJOJIOIIO

Salida

4