Problembeskrivning

JOIOI-tornet är ett spel för $1$ spelare som spelas med skivor.

Detta spel spelas med ett antal skivor, där varje skiva har ett av tecknen J, O eller I skrivet på sig. Skivorna har sinsemellan olika diametrar, och i början av spelet är dessa skivor staplade nerifrån och upp i fallande ordning efter diameter. Med hjälp av dessa skivor vill du bygga så många mini-JOIOI-torn som möjligt. Ett mini-JOIOI-torn består av $3$ skivor och bildar JOI eller IOI när det läses i stigande ordning efter skivornas diameter. Samma skiva får dock inte användas $2$ eller fler gånger.

Figur: Av JOIOII kan man bygga $2$ mini-JOIOI-torn

Uppgift

Tecknen som står på de förberedda skivorna ges som en sträng $S$ av längd $N$ i stigande ordning efter skivornas diameter. Skriv ett program för att hitta det maximala antalet mini-JOIOI-torn som kan byggas med dessa skivor.

Begränsningar

• $1 \le N \le 1000000$: Längden på strängen $S$.

Indata

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

• På den $1$:a raden står ett heltal $N$. $N$ representerar längden på strängen $S$.
• På den $2$:a raden står en sträng $S$.

Utdata

Skriv ut ett heltal på $1$ rad till standard ut som representerar det maximala antalet mini-JOIOI-torn som kan byggas.

Delpoäng

• För $10\%$ av poängen i testdata gäller $N \le 15$.
• För $30\%$ av poängen i testdata gäller $N \le 50$.
• För $50\%$ av poängen i testdata gäller $N \le 3000$.

Exempel 1

Indata

6
JOIIOI

Utdata

2

JOIIOI innehåller JOI och IOI som delsekvenser $1$ gång vardera, så antalet mini-JOIOI-torn som kan byggas är $2$.

Exempel 2

Indata

5
JOIOI

Utdata

1

Även om den innehåller JOI och IOI som delsekvenser, kan ett tecken inte användas $2$ eller fler gånger, så de kan inte plockas ut samtidigt.

Exempel 3

Indata

6
JOIOII

Utdata

2

Detta exempel motsvarar exemplet i problembeskrivningen.

Exempel 4

Indata

15
JJOIIOOJOJIOIIO

Utdata

4