Treść zadania

Ćwicząc programowanie przed finałem JOI, zauważyłeś, że w tegorocznych eliminacjach JOI były wyłącznie zadania liczbowe i ani jednego zadania na napisy. Postanowiłeś więc potajemnie podszkolić się w zadaniach na napisy, aby wyprzedzić swoich rywali. Przeglądając dawne zadania z JOI, odkryłeś, że powinieneś oswoić się z napisami składającymi się z $3$ rodzajów znaków: J, O oraz I. Rozważmy takie napisy. Wpadłeś na zadanie „Odpowiedz, czy dany napis zawiera JOI jako podciąg spójny”, które od razu rozwiązałeś. Chcąc rozwiązać zadanie na wyższym poziomie, ułożyłeś następujące zadanie.

Napis $t$ jest podciągiem spójnym napisu $s$, jeśli $s$ można otrzymać poprzez dopisanie pewnej liczby znaków (dozwolone jest także $0$ znaków) na początku i na końcu napisu $t$. Na przykład JJOOII jest podciągiem spójnym napisu OJJOOIIOJOI. Z drugiej strony JOI nie jest podciągiem spójnym napisu JOOI.

Ponadto dla liczby całkowitej $k$ większej lub równej $0$, napis-JOI poziomu $k$ to napis utworzony przez ustawienie kolejno $k$ znaków J, $k$ znaków O oraz $k$ znaków I. Na przykład JJOOII jest napisem-JOI poziomu $2$.

Chcemy znaleźć ten o maksymalnym poziomie spośród napisów-JOI będących podciągami spójnymi danego napisu.

Zadanie

Mając dany napis $S$ o długości $N$, składający się z $3$ rodzajów znaków J, O oraz I, napisz program, który wyznaczy maksymalną wartość $k$, dla której napis-JOI poziomu $k$ jest podciągiem spójnym napisu $S$.

Ograniczenia

• $1 \le N \le 1000000 \ (= 10^6)$: długość napisu $S$.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• W $1$-szym wierszu zapisany jest napis $S$ składający się z $3$ rodzajów znaków J, O oraz I.

Wyjście

Wypisz na standardowe wyjście w $1$ wierszu liczbę całkowitą oznaczającą maksymalną wartość $k$, dla której napis-JOI poziomu $k$ jest podciągiem spójnym napisu $S$.

Podzadania

• Dla $20\%$ punktów w danych testowych spełniony jest warunek $N \le 100$.

Przykład 1

Wejście

OJJOOIIOJOI

Wyjście

2

OJJOOIIOJOI zawiera JJOOII, czyli napis-JOI poziomu $2$, jako podciąg spójny i nie zawiera żadnego napisu-JOI poziomu $3$ ani wyższego jako podciągu spójnego.

Przykład 2

Wejście

IJJIIJJJ

Wyjście

0

Napis-JOI poziomu $0$ to napis o długości $0$.

Przykład 3

Wejście

JOIJOIJOIJOIJOI

Wyjście

1

Przykład 4

Wejście

OOJJJJJJOOOOIIIII

Wyjście

4