Opis problemu

JOI posiada po $0$ lub więcej sztuk każdego z $3$ rodzajów pieczątek: pieczątki z kółkiem, pieczątki z krzyżykiem oraz pieczątki z kółkiem i krzyżykiem. Są to pieczątki, którymi można odbijać na papierze znaki kółka lub krzyżyka.

Użycie pieczątki z kółkiem powoduje odbicie $1$ kółka, a użycie pieczątki z krzyżykiem powoduje odbicie $1$ krzyżyka. Użycie pieczątki z kółkiem i krzyżykiem powoduje odbicie w jednym poziomym rzędzie $1$ kółka oraz $1$ krzyżyka, przy czym zmieniając orientację pieczątki, można odbić ją tak, aby krzyżyk znalazł się na prawo od kółka, lub tak, aby kółko znalazło się na prawo od krzyżyka.

JOI użył każdej posiadanej przez siebie pieczątki dokładnie $1$ raz w pewnej kolejności, odbijając na papierze w poziomym rzędzie ciąg kółek i krzyżyków. Odbity ciąg kółek i krzyżyków jest reprezentowany przez napis $S$. $S$ jest napisem długości $N$ złożonym ze znaków O oraz X; jeśli $S_i = $ O, oznacza to, że $i$-ty od lewej znak odbity przez JOI jest kółkiem, a jeśli $S_i =$ X, oznacza to, że jest on krzyżykiem ($1 \le i \le N$).

Nie wiesz, ile pieczątek ma JOI, ale znasz odbity przez niego ciąg kółek i krzyżyków. Na podstawie odbitego ciągu kółek i krzyżyków wyznacz maksymalną możliwą liczbę pieczątek z kółkiem i krzyżykiem, jaką może posiadać JOI.

Ograniczenia

• $1 \le N \le 100000 (= 10^5)$
• $S$ jest napisem długości $N$.
• Każdy znak napisu $S$ to O lub X.

Wejście / Wyjście

Wejście
Wejście podawane jest ze standardowego wejścia w następującym formacie:
$N$
$S$

Wyjście
Wypisz maksymalną możliwą liczbę pieczątek z kółkiem i krzyżykiem, jaką może posiadać JOI.

Przykłady wejścia / wyjścia

Przykładowe wejście 1

5
OXXOX

Przykładowe wyjście 1

2

Znaki odbite przez JOI to kolejno od lewej: kółko, krzyżyk, krzyżyk, kółko, krzyżyk. Jeśli JOI ma odpowiednio $0, 1, 2$ pieczątek z kółkiem, pieczątek z krzyżykiem oraz pieczątek z kółkiem i krzyżykiem, to może odbić takie znaki, używając pieczątek w następującej kolejności:

• Używa $1$. pieczątki z kółkiem i krzyżykiem, aby odbić kółko i krzyżyk w tej kolejności.
• Na prawo od nich używa $2$. pieczątki z kółkiem i krzyżykiem, aby odbić krzyżyk i kółko w tej kolejności.
• Na koniec na prawo od nich używa pieczątki z krzyżykiem, aby odbić krzyżyk.

Ponieważ przypadek posiadania $3$ lub więcej pieczątek z kółkiem i krzyżykiem jest niemożliwy, należy wypisać $2$.

Przykładowe wejście 2

14
OXOXOXOXXOXOXO

Przykładowe wyjście 2

7

Przykładowe wejście 3

10
OOOOOOOOOO

Przykładowe wyjście 3

0