Tehtävänanto

JOIOI-torni on $1$ pelaajan peli, jota pelataan kiekkojen avulla.

Tätä peliä pelataan käyttäen useita kiekkoja, joista jokaiseen on kirjoitettu jokin merkeistä J, O tai I. Kiekkojen halkaisijat ovat keskenään erisuuria, ja pelin alkaessa nämä kiekot on pinottu alhaalta ylöspäin halkaisijan mukaisessa laskevassa järjestyksessä. Haluat muodostaa näitä kiekkoja käyttäen mahdollisimman monta mini-JOIOI-tornia. Mini-JOIOI-torni koostuu $3$ kiekosta, ja kiekkojen halkaisijan mukaisessa kasvavassa järjestyksessä luettuna siitä muodostuu JOI tai IOI. Samaa kiekkoa ei kuitenkaan voi käyttää $2$ tai useampaa kertaa.

Kuva: Merkkijonosta JOIOII voidaan muodostaa $2$ mini-JOIOI-tornia

Tehtävä

Valmisteltuihin kiekkoihin kirjoitetut merkit annetaan kiekkojen halkaisijan mukaisessa kasvavassa järjestyksessä pituuden $N$ merkkijonona $S$. Kirjoita ohjelma, joka etsii näitä kiekkoja käyttäen muodostettavissa olevien mini-JOIOI-tornien lukumäärän suurimman mahdollisen arvon.

Rajoitukset

• $1 \le N \le 1000000$: Merkkijonon $S$ pituus.

Syöte

Lue seuraavat tiedot vakiosyötteestä.

• $1$. rivillä on kokonaisluku $N$. $N$ ilmaisee merkkijonon $S$ pituuden.
• $2$. rivillä on merkkijono $S$.

Tuloste

Tulosta vakiotulosteeseen $1$ riville kokonaisluku, joka ilmaisee muodostettavissa olevien mini-JOIOI-tornien lukumäärän suurimman mahdollisen arvon.

Osatehtävät

• Arvosteluaineiston pisteistä $10\%$ osuudessa pätee $N \le 15$.
• Arvosteluaineiston pisteistä $30\%$ osuudessa pätee $N \le 50$.
• Arvosteluaineiston pisteistä $50\%$ osuudessa pätee $N \le 3000$.

Esimerkki 1

Syöte

6
JOIIOI

Tuloste

2

JOIIOI sisältää alijonoina merkkijonot JOI ja IOI, kummankin $1$ kerran, joten muodostettavissa olevien mini-JOIOI-tornien lukumäärä on $2$.

Esimerkki 2

Syöte

5
JOIOI

Tuloste

1

Vaikka se sisältää alijonoina merkkijonot JOI ja IOI, samaa merkkiä ei voi käyttää $2$ tai useampaa kertaa, joten niitä ei voida poimia samanaikaisesti.

Esimerkki 3

Syöte

6
JOIOII

Tuloste

2

Tämä esimerkki vastaa tehtävänannossa esitettyä esimerkkiä.

Esimerkki 4

Syöte

15
JJOIIOOJOJIOIIO

Tuloste

4