Lýsing á verkefni

Þegar þú varst að æfa forritun fyrir úrslitakeppni JOI tókstu eftir því að forkeppni JOI í ár innihélt aðeins töluleg verkefni en engin strengjaverkefni. Því ákvaðstu að verða í laumi mjög fær í strengjaverkefnum til að ná forskoti á keppinauta þína. Þegar þú skoðaðir eldri JOI verkefni komstu að því að þú ættir að venjast strengjum sem samanstanda af $3$ tegundum stafa: J, O og I. Við skulum skoða slíka strengi. Þér datt í hug verkefnið „Svaraðu hvort gefinn strengur innihaldi JOI sem hlutstreng“, sem þú leystir samstundis. Þar sem þú vildir leysa erfiðara verkefni bjóstu til eftirfarandi verkefni.

Strengur $t$ er hlutstrengur í streng $s$ ef hægt er að fá $s$ með því að bæta einhverjum fjölda stafa ($0$ stafir eru líka leyfðir) fremst og aftast við $t$. Til dæmis er JJOOII hlutstrengur í OJJOOIIOJOI. Hins vegar er JOI ekki hlutstrengur í JOOI.

Auk þess, fyrir heiltölu $k$ sem er stærri en eða jöfn $0$, er JOI-strengur af stigi $k$ strengur sem myndast með því að raða $k$ stöfum J, $k$ stöfum O og $k$ stöfum I í þessari röð. Til dæmis er JJOOII JOI-strengur af stigi $2$.

Við viljum finna þann sem hefur hæsta stigið meðal þeirra JOI-strengja sem eru hlutstrengir í gefna strengnum.

Verkefni

Gefinn er strengur $S$ af lengd $N$ sem samanstendur af $3$ tegundum stafa: J, O og I. Skrifaðu forrit til að finna hæsta gildið á $k$ þannig að JOI-strengurinn af stigi $k$ sé hlutstrengur í $S$.

Takmarkanir

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

Inntak

Lestu eftirfarandi gögn úr staðalinntaki.

• Á $1$. línu er skrifaður strengur $S$ sem samanstendur af $3$ tegundum stafa: J, O og I.

Úttak

Skrifaðu út í staðalúttak á $1$ línu heiltölu sem táknar hæsta gildið á $k$ þannig að JOI-strengurinn af stigi $k$ sé hlutstrengur í $S$.

Undirverkefni

• Fyrir $20\%$ stiga í prófunargögnum gildir $N \le 100$.

Dæmi 1

Inntak

OJJOOIIOJOI

Úttak

2

OJJOOIIOJOI inniheldur JJOOII, sem er JOI-strengur af stigi $2$, sem hlutstreng, og inniheldur engan JOI-streng af stigi $3$ eða hærra sem hlutstreng.

Dæmi 2

Inntak

IJJIIJJJ

Úttak

0

JOI-strengurinn af stigi $0$ er strengur af lengd $0$.

Dæmi 3

Inntak

JOIJOIJOIJOIJOI

Úttak

1

Dæmi 4

Inntak

OOJJJJJJOOOOIIIII

Úttak

4