Problembeskrivelse
Mens du øvde på programmering til JOI-finalen, la du merke til at årets kvalifiseringsrunde i JOI bare hadde numeriske oppgaver og ingen strengoppgaver. Derfor bestemte du deg for å i hemmelighet bli skikkelig god på strengoppgaver for å få et forsprang på rivalene dine. Da du så på tidligere JOI-oppgaver, fant du ut at du burde venne deg til strenger som består av de $3$ tegntypene J, O og I. La oss betrakte slike strenger. Du kom på oppgaven «Svar på om en gitt streng har JOI som delstreng», som du løste umiddelbart. Siden du ville løse en oppgave på et høyere nivå, lagde du følgende oppgave.
En streng $t$ er en delstreng av en streng $s$ hvis $s$ kan oppnås ved å legge til et antall tegn ($0$ tegn er også tillatt) på begynnelsen og slutten av $t$. For eksempel er JJOOII en delstreng av OJJOOIIOJOI. På den annen side er JOI ikke en delstreng av JOOI.
Videre, for et heltall $k$ større enn eller lik $0$, er en JOI-streng av nivå $k$ en streng dannet ved å sette opp $k$ tegn J, $k$ tegn O og $k$ tegn I i denne rekkefølgen. For eksempel er JJOOII en JOI-streng av nivå $2$.
Vi ønsker å finne den med maksimalt nivå blant JOI-strengene som er delstrenger av den gitte strengen.
Oppgave
Gitt en streng $S$ med lengde $N$ som består av de $3$ tegntypene J, O og I, skriv et program for å finne den maksimale verdien av $k$ slik at JOI-strengen av nivå $k$ er en delstreng av $S$.
Begrensninger
- $1 \le N \le 1000000 \ (= 10^6)$: Lengden på $S$.
Inndata
Les følgende data fra standard inndata.
- På den $1$. linjen står det en streng $S$ som består av de $3$ tegntypene
J,OogI.
Utdata
Skriv ut på standard utdata på $1$ linje et heltall som representerer den maksimale verdien av $k$ slik at JOI-strengen av nivå $k$ er en delstreng av $S$.
Deloppgaver
- For $20\%$ av poengene i testdataene er $N \le 100$ oppfylt.
Eksempel 1
Inndata
OJJOOIIOJOI
Utdata
2
OJJOOIIOJOI inneholder JJOOII, som er JOI-strengen av nivå $2$, som delstreng, og inneholder ingen JOI-streng av nivå $3$ eller høyere som delstreng.
Eksempel 2
Inndata
IJJIIJJJ
Utdata
0
JOI-strengen av nivå $0$ er en streng med lengde $0$.
Eksempel 3
Inndata
JOIJOIJOIJOIJOI
Utdata
1
Eksempel 4
Inndata
OOJJJJJJOOOOIIIII
Utdata
4