Problembeschreibung

Als du für die JOI-Endrunde das Programmieren geübt hast, ist dir aufgefallen, dass die diesjährige JOI-Vorrunde nur numerische Aufgaben und keine Zeichenkettenaufgaben enthielt. Also hast du beschlossen, heimlich richtig gut in Zeichenkettenaufgaben zu werden, um deinen Rivalen einen Schritt voraus zu sein. Beim Durchsehen früherer JOI-Aufgaben hast du festgestellt, dass man sich an Zeichenketten gewöhnen sollte, die aus den $3$ Zeichenarten J, O und I bestehen. Betrachten wir solche Zeichenketten. Dir ist die Aufgabe „Antworte, ob eine gegebene Zeichenkette JOI als Teilzeichenkette enthält“ eingefallen, die du sofort gelöst hast. Da du eine anspruchsvollere Aufgabe lösen wolltest, hast du die folgende Aufgabe erstellt.

Eine Zeichenkette $t$ ist eine Teilzeichenkette einer Zeichenkette $s$, wenn $s$ dadurch erhalten werden kann, dass man am Anfang und am Ende von $t$ einige Zeichen ($0$ Zeichen sind ebenfalls erlaubt) anfügt. Zum Beispiel ist JJOOII eine Teilzeichenkette von OJJOOIIOJOI. Andererseits ist JOI keine Teilzeichenkette von JOOI.

Außerdem ist für eine ganze Zahl $k$ größer oder gleich $0$ eine JOI-Zeichenkette der Stufe $k$ eine Zeichenkette, die durch das Aneinanderreihen von $k$ Zeichen J, $k$ Zeichen O und $k$ Zeichen I in dieser Reihenfolge entsteht. Zum Beispiel ist JJOOII eine JOI-Zeichenkette der Stufe $2$.

Wir wollen unter den JOI-Zeichenketten, die Teilzeichenketten der gegebenen Zeichenkette sind, diejenige mit der maximalen Stufe finden.

Aufgabe

Gegeben ist eine Zeichenkette $S$ der Länge $N$, die aus den $3$ Zeichenarten J, O und I besteht. Schreibe ein Programm, das den maximalen Wert von $k$ bestimmt, sodass die JOI-Zeichenkette der Stufe $k$ eine Teilzeichenkette von $S$ ist.

Beschränkungen

• $1 \le N \le 1000000 \ (= 10^6)$: Die Länge von $S$.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• In der $1$-ten Zeile steht eine Zeichenkette $S$, die aus den $3$ Zeichenarten J, O und I besteht.

Ausgabe

Gib auf der Standardausgabe in $1$ Zeile eine ganze Zahl aus, die den maximalen Wert von $k$ darstellt, sodass die JOI-Zeichenkette der Stufe $k$ eine Teilzeichenkette von $S$ ist.

Teilaufgaben

• Für $20\%$ der Punkte in den Bewertungsdaten gilt $N \le 100$.

Beispiel 1

Eingabe

OJJOOIIOJOI

Ausgabe

2

OJJOOIIOJOI enthält JJOOII, also die JOI-Zeichenkette der Stufe $2$, als Teilzeichenkette und enthält keine JOI-Zeichenkette der Stufe $3$ oder höher als Teilzeichenkette.

Beispiel 2

Eingabe

IJJIIJJJ

Ausgabe

0

Die JOI-Zeichenkette der Stufe $0$ ist eine Zeichenkette der Länge $0$.

Beispiel 3

Eingabe

JOIJOIJOIJOIJOI

Ausgabe

1

Beispiel 4

Eingabe

OOJJJJJJOOOOIIIII

Ausgabe

4