Problembeschreibung

JOI besitzt jeweils $0$ oder mehr Exemplare von $3$ Arten von Stempeln: Kreisstempel, Kreuzstempel und Kreis-Kreuz-Stempel. Mit diesen Stempeln lassen sich Kreis- oder Kreuzsymbole auf Papier drucken.

Mit einem Kreisstempel wird $1$ Kreis gedruckt, und mit einem Kreuzstempel wird $1$ Kreuz gedruckt. Mit einem Kreis-Kreuz-Stempel werden $1$ Kreis und $1$ Kreuz nebeneinander in einer horizontalen Reihe gedruckt, wobei durch Drehen des Stempels entweder das Kreuz rechts vom Kreis oder der Kreis rechts vom Kreuz gedruckt werden kann.

JOI hat jeden seiner Stempel genau $1$-mal in einer geeigneten Reihenfolge benutzt, um Kreise und Kreuze in einer horizontalen Reihe auf Papier zu drucken. Die Folge der gedruckten Kreise und Kreuze wird durch eine Zeichenkette $S$ dargestellt. $S$ ist eine aus O und X bestehende Zeichenkette der Länge $N$; falls $S_i = $ O ist, bedeutet dies, dass das $i$-te von JOI gedruckte Symbol von links ein Kreis ist, und falls $S_i =$ X ist, bedeutet dies, dass es ein Kreuz ist ($1 \le i \le N$).

Du weißt zwar nicht, wie viele Stempel JOI besitzt, kennst aber die von JOI gedruckte Folge von Kreisen und Kreuzen. Bestimme anhand der gedruckten Folge von Kreisen und Kreuzen die maximal mögliche Anzahl an Kreis-Kreuz-Stempeln, die JOI besitzen kann.

Einschränkungen

• $1 \le N \le 100000 (= 10^5)$
• $S$ ist eine Zeichenkette der Länge $N$.
• Jedes Zeichen von $S$ ist O oder X.

Eingabe / Ausgabe

Eingabe
Die Eingabe erfolgt über die Standardeingabe im folgenden Format:
$N$
$S$

Ausgabe
Gib die maximal mögliche Anzahl an Kreis-Kreuz-Stempeln aus, die JOI besitzen kann.

Ein- und Ausgabebeispiele

Beispieleingabe 1

5
OXXOX

Beispielausgabe 1

2

Die von JOI gedruckten Symbole lauten von links nach rechts: Kreis, Kreuz, Kreuz, Kreis, Kreuz. Wenn JOI jeweils $0, 1, 2$ Kreisstempel, Kreuzstempel bzw. Kreis-Kreuz-Stempel besitzt, kann er die Symbole auf diese Weise drucken, indem er die Stempel in folgender Reihenfolge benutzt:

• Mit dem $1$. Kreis-Kreuz-Stempel werden ein Kreis und ein Kreuz in dieser Reihenfolge gedruckt.
• Rechts davon werden mit dem $2$. Kreis-Kreuz-Stempel ein Kreuz und ein Kreis in dieser Reihenfolge gedruckt.
• Schließlich wird rechts davon mit dem Kreuzstempel ein Kreuz gedruckt.

Da es unmöglich ist, dass er $3$ oder mehr Kreis-Kreuz-Stempel besitzt, wird $2$ ausgegeben.

Beispieleingabe 2

14
OXOXOXOXXOXOXO

Beispielausgabe 2

7

Beispieleingabe 3

10
OOOOOOOOOO

Beispielausgabe 3

0