Tehtävänanto

Harjoitellessasi ohjelmointia JOI-loppukilpailua varten huomasit, että tämän vuoden JOI-alkukilpailussa oli vain numeerisia tehtäviä eikä yhtään merkkijonotehtävää. Niinpä päätit salaa kehittyä vahvaksi merkkijonotehtävissä saadaksesi etumatkaa kilpakumppaneihisi. Tutkiessasi aiempia JOI-tehtäviä huomasit, että sinun kannattaa totutella merkkijonoihin, jotka koostuvat $3$ merkkityypistä J, O ja I. Tarkastellaan tällaisia merkkijonoja. Keksit tehtävän "Vastaa, sisältääkö annettu merkkijono osajononaan merkkijonon JOI", jonka ratkaisit heti. Halutessasi ratkaista korkeatasoisemman tehtävän лаadit seuraavan tehtävän.

Merkkijono $t$ on merkkijonon $s$ osajono, jos $s$ voidaan saada lisäämällä jokin määrä merkkejä (myös $0$ merkkiä on sallittu) merkkijonon $t$ alkuun ja loppuun. Esimerkiksi JJOOII on merkkijonon OJJOOIIOJOI osajono. Toisaalta JOI ei ole merkkijonon JOOI osajono.

Lisäksi, kun $k$ on kokonaisluku, joka on suurempi tai yhtä suuri kuin $0$, tason $k$ JOI-merkkijono on merkkijono, joka muodostuu asettamalla peräkkäin $k$ merkkiä J, $k$ merkkiä O ja $k$ merkkiä I tässä järjestyksessä. Esimerkiksi JJOOII on tason $2$ JOI-merkkijono.

Haluamme löytää annetun merkkijonon osajonoina olevista JOI-merkkijonoista sen, jonka taso on suurin.

Tehtävä

Annettuna on pituuden $N$ merkkijono $S$, joka koostuu $3$ merkkityypistä J, O ja I. Kirjoita ohjelma, joka etsii suurimman sellaisen luvun $k$ arvon, jolla tason $k$ JOI-merkkijono on merkkijonon $S$ osajono.

Rajoitukset

• $1 \le N \le 1000000 \ (= 10^6)$: Merkkijonon $S$ pituus.

Syöte

Lue seuraavat tiedot vakiosyötteestä.

• $1$. rivillä on merkkijono $S$, joka koostuu $3$ merkkityypistä J, O ja I.

Tuloste

Tulosta vakiotulosteeseen $1$ riville kokonaisluku, joka ilmaisee suurimman sellaisen luvun $k$ arvon, jolla tason $k$ JOI-merkkijono on merkkijonon $S$ osajono.

Osatehtävät

• Arvosteluaineiston pisteistä $20\%$ osuudessa pätee $N \le 100$.

Esimerkki 1

Syöte

OJJOOIIOJOI

Tuloste

2

OJJOOIIOJOI sisältää osajononaan merkkijonon JJOOII, joka on tason $2$ JOI-merkkijono, eikä se sisällä osajononaan mitään tason $3$ tai sitä korkeamman tason JOI-merkkijonoa.

Esimerkki 2

Syöte

IJJIIJJJ

Tuloste

0

Tason $0$ JOI-merkkijono on pituuden $0$ merkkijono.

Esimerkki 3

Syöte

JOIJOIJOIJOIJOI

Tuloste

1

Esimerkki 4

Syöte

OOJJJJJJOOOOIIIII

Tuloste

4