Problembeskrivning

När du övade programmering inför JOI-finalen märkte du att årets kvalomgång i JOI bara hade numeriska problem och inga strängproblem. Därför bestämde du dig för att i hemlighet bli riktigt bra på strängproblem för att få ett försprång mot dina rivaler. När du tittade på tidigare JOI-problem insåg du att du borde vänja dig vid strängar som består av de $3$ teckentyperna J, O och I. Låt oss betrakta sådana strängar. Du kom på problemet "Svara på om en given sträng har JOI som delsträng", vilket du löste omedelbart. Eftersom du ville lösa ett problem på högre nivå skapade du följande problem.

En sträng $t$ är en delsträng av en sträng $s$ om $s$ kan erhållas genom att lägga till ett antal tecken ($0$ tecken är också tillåtet) i början och i slutet av $t$. Till exempel är JJOOII en delsträng av OJJOOIIOJOI. Å andra sidan är JOI inte en delsträng av JOOI.

För ett heltal $k$ större än eller lika med $0$ är dessutom en JOI-sträng av nivå $k$ en sträng som bildas genom att placera $k$ tecken J, $k$ tecken O och $k$ tecken I i denna ordning. Till exempel är JJOOII en JOI-sträng av nivå $2$.

Vi vill hitta den med högst nivå bland de JOI-strängar som är delsträngar av den givna strängen.

Uppgift

Givet en sträng $S$ av längd $N$ som består av de $3$ teckentyperna J, O och I, skriv ett program för att hitta det maximala värdet på $k$ sådant att JOI-strängen av nivå $k$ är en delsträng av $S$.

Begränsningar

• $1 \le N \le 1000000 \ (= 10^6)$: Längden på $S$.

Indata

Läs följande data från standard in.

• På den $1$:a raden står en sträng $S$ som består av de $3$ teckentyperna J, O och I.

Utdata

Skriv ut ett heltal på $1$ rad till standard ut som representerar det maximala värdet på $k$ sådant att JOI-strängen av nivå $k$ är en delsträng av $S$.

Delpoäng

• För $20\%$ av poängen i testdata gäller $N \le 100$.

Exempel 1

Indata

OJJOOIIOJOI

Utdata

2

OJJOOIIOJOI innehåller JJOOII, som är JOI-strängen av nivå $2$, som delsträng, och innehåller ingen JOI-sträng av nivå $3$ eller högre som delsträng.

Exempel 2

Indata

IJJIIJJJ

Utdata

0

JOI-strängen av nivå $0$ är en sträng av längd $0$.

Exempel 3

Indata

JOIJOIJOIJOIJOI

Utdata

1

Exempel 4

Indata

OOJJJJJJOOOOIIIII

Utdata

4