Problembeschreibung

Der Turm von JOIOI ist ein Spiel für $1$ Person, das mit Scheiben gespielt wird.

Dieses Spiel wird mit mehreren Scheiben gespielt, auf denen jeweils eines der Zeichen J, O oder I steht. Die Scheiben haben paarweise unterschiedliche Durchmesser, und zu Spielbeginn sind diese Scheiben in absteigender Reihenfolge ihres Durchmessers von unten nach oben gestapelt. Mithilfe dieser Scheiben möchtest du so viele Mini-JOIOI-Türme wie möglich bauen. Ein Mini-JOIOI-Turm besteht aus $3$ Scheiben und ergibt in aufsteigender Reihenfolge des Scheibendurchmessers gelesen JOI oder IOI. Allerdings darf dieselbe Scheibe nicht $2$-mal oder öfter verwendet werden.

Abbildung: Aus JOIOII lassen sich $2$ Mini-JOIOI-Türme bauen

Aufgabe

Die auf den vorbereiteten Scheiben stehenden Zeichen werden in aufsteigender Reihenfolge des Scheibendurchmessers als Zeichenkette $S$ der Länge $N$ gegeben. Schreibe ein Programm, das die maximale Anzahl von Mini-JOIOI-Türmen bestimmt, die mit diesen Scheiben gebaut werden können.

Beschränkungen

• $1 \le N \le 1000000$: Die Länge der Zeichenkette $S$.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• In der $1$-ten Zeile steht eine ganze Zahl $N$. $N$ gibt die Länge der Zeichenkette $S$ an.
• In der $2$-ten Zeile steht eine Zeichenkette $S$.

Ausgabe

Gib auf der Standardausgabe in $1$ Zeile eine ganze Zahl aus, die die maximale Anzahl der Mini-JOIOI-Türme darstellt, die gebaut werden können.

Teilaufgaben

• Für $10\%$ der Punkte in den Bewertungsdaten gilt $N \le 15$.
• Für $30\%$ der Punkte in den Bewertungsdaten gilt $N \le 50$.
• Für $50\%$ der Punkte in den Bewertungsdaten gilt $N \le 3000$.

Beispiel 1

Eingabe

6
JOIIOI

Ausgabe

2

JOIIOI enthält JOI und IOI jeweils $1$-mal als Teilfolge, sodass $2$ Mini-JOIOI-Türme gebaut werden können.

Beispiel 2

Eingabe

5
JOIOI

Ausgabe

1

Zwar sind JOI und IOI als Teilfolgen enthalten, aber da ein Zeichen nicht $2$-mal oder öfter verwendet werden darf, können sie nicht gleichzeitig entnommen werden.

Beispiel 3

Eingabe

6
JOIOII

Ausgabe

2

Dieses Beispiel entspricht dem Beispiel in der Problembeschreibung.

Beispiel 4

Eingabe

15
JJOIIOOJOJIOIIO

Ausgabe

4