Treść zadania

Wieża JOIOI to jednoosobowa ($1$ gracz) gra wykorzystująca krążki.

Gra ta rozgrywana jest przy użyciu kilku krążków, z których każdy ma napisany jeden ze znaków J, O lub I. Krążki mają parami różne średnice, a na początku gry krążki te są ułożone jeden na drugim od dołu do góry w kolejności malejących średnic. Używając tych krążków, chcesz zbudować jak najwięcej miniwież JOIOI. Miniwieża JOIOI składa się z $3$ krążków i czytana w kolejności rosnących średnic krążków daje napis JOI lub IOI. Jednak tego samego krążka nie można użyć $2$ ani więcej razy.

Rysunek: Z JOIOII można zbudować $2$ miniwieże JOIOI

Zadanie

Znaki zapisane na przygotowanych krążkach są podane w kolejności rosnących średnic krążków jako napis $S$ o długości $N$. Napisz program, który wyznaczy maksymalną liczbę miniwież JOIOI, jakie można zbudować przy użyciu tych krążków.

Ograniczenia

• $1 \le N \le 1000000$: długość napisu $S$.

Wejście

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

• W $1$-szym wierszu zapisana jest liczba całkowita $N$. $N$ oznacza długość napisu $S$.
• W $2$-gim wierszu zapisany jest napis $S$.

Wyjście

Wypisz na standardowe wyjście w $1$ wierszu liczbę całkowitą oznaczającą maksymalną liczbę miniwież JOIOI, jakie można zbudować.

Podzadania

• Dla $10\%$ punktów w danych testowych spełniony jest warunek $N \le 15$.
• Dla $30\%$ punktów w danych testowych spełniony jest warunek $N \le 50$.
• Dla $50\%$ punktów w danych testowych spełniony jest warunek $N \le 3000$.

Przykład 1

Wejście

6
JOIIOI

Wyjście

2

JOIIOI zawiera JOI oraz IOI po $1$ razie jako podciągi, zatem liczba miniwież JOIOI, jakie można zbudować, wynosi $2$.

Przykład 2

Wejście

5
JOIOI

Wyjście

1

Wprawdzie napis zawiera JOI oraz IOI jako podciągi, ale tego samego znaku nie można użyć $2$ ani więcej razy, więc nie można wybrać ich jednocześnie.

Przykład 3

Wejście

6
JOIOII

Wyjście

2

Ten przykład odpowiada przykładowi z treści zadania.

Przykład 4

Wejście

15
JJOIIOOJOJIOIIO

Wyjście

4