Descrizione del problema

La Torre di JOIOI è un gioco per $1$ giocatore che utilizza dei dischi.

Questo gioco si svolge utilizzando diversi dischi, su ciascuno dei quali è scritto uno dei caratteri J, O oppure I. I dischi hanno diametri tutti diversi tra loro e, all'inizio del gioco, questi dischi sono impilati dal basso verso l'alto in ordine decrescente di diametro. Utilizzando questi dischi, vuoi costruire il maggior numero possibile di mini-torri JOIOI. Una mini-torre JOIOI è composta da $3$ dischi e si legge JOI oppure IOI quando viene letta in ordine crescente di diametro dei dischi. Tuttavia, non è possibile utilizzare lo stesso disco $2$ o più volte.

Figura: Da JOIOII si possono costruire $2$ mini-torri JOIOI

Compito

I caratteri scritti sui dischi preparati vengono forniti come una stringa $S$ di lunghezza $N$ in ordine crescente di diametro dei dischi. Scrivi un programma per trovare il valore massimo del numero di mini-torri JOIOI che possono essere costruite utilizzando questi dischi.

Limiti

• $1 \le N \le 1000000$: La lunghezza della stringa $S$.

Input

Leggi i seguenti dati dallo standard input.

• Sulla $1$-a riga è scritto un intero $N$. $N$ rappresenta la lunghezza della stringa $S$.
• Sulla $2$-a riga è scritta una stringa $S$.

Output

Stampa sullo standard output su $1$ riga un intero che rappresenta il valore massimo del numero di mini-torri JOIOI che possono essere costruite.

Sottoproblemi

• Per il $10\%$ dei punti nei dati di valutazione, vale $N \le 15$.
• Per il $30\%$ dei punti nei dati di valutazione, vale $N \le 50$.
• Per il $50\%$ dei punti nei dati di valutazione, vale $N \le 3000$.

Esempio 1

Input

6
JOIIOI

Output

2

JOIIOI contiene JOI e IOI $1$ volta ciascuno come sottosequenza, quindi il numero di mini-torri JOIOI che si possono costruire è $2$.

Esempio 2

Input

5
JOIOI

Output

1

Sebbene contenga JOI e IOI come sottosequenze, non è possibile usare un carattere $2$ o più volte, quindi non possono essere estratti contemporaneamente.

Esempio 3

Input

6
JOIOII

Output

2

Questo esempio corrisponde all'esempio nella descrizione del problema.

Esempio 4

Input

15
JJOIIOOJOJIOIIO

Output

4