Tehtävänanto

JOI:lla on $0$ tai enemmän kutakin $3$ leimasintyypistä: ympyräleimasimia, ristileimasimia ja ympyrä-risti-leimasimia. Näillä leimasimilla voidaan painaa paperille ympyrä- ja ristimerkkejä.

Ympyräleimasinta käytettäessä painetaan $1$ ympyrä ja ristileimasinta käytettäessä $1$ risti. Ympyrä-risti-leimasinta käytettäessä painetaan vaakasuoraan riviin $1$ ympyrä ja $1$ risti, ja leimasimen suuntaa kääntämällä ne voidaan painaa joko niin, että risti tulee ympyrän oikealle puolelle, tai niin, että ympyrä tulee ristin oikealle puolelle.

JOI käytti jokaista omistamaansa leimasinta täsmälleen $1$ kerran sopivassa järjestyksessä ja painoi paperille vaakasuoran rivin ympyröitä ja ristejä. Painettujen ympyröiden ja ristien jono esitetään merkkijonona $S$. $S$ on merkeistä O ja X koostuva pituuden $N$ merkkijono; jos $S_i = $ O, se tarkoittaa, että JOI:n painamista merkeistä vasemmalta lukien $i$-s on ympyrä, ja jos $S_i =$ X, se tarkoittaa, että merkki on risti ($1 \le i \le N$).

Et tiedä JOI:n omistamien leimasinten lukumäärää, mutta tiedät JOI:n painaman ympyröiden ja ristien jonon. Selvitä painetun ympyröiden ja ristien jonon perusteella suurin mahdollinen ympyrä-risti-leimasinten lukumäärä, joka JOI:lla voi olla.

Rajoitukset

• $1 \le N \le 100000 (= 10^5)$
• $S$ on pituuden $N$ merkkijono.
• Jokainen merkkijonon $S$ merkki on O tai X.

Syöte ja tuloste

Syöte
Syöte annetaan vakiosyötteestä seuraavassa muodossa:
$N$
$S$

Tuloste
Tulosta suurin mahdollinen ympyrä-risti-leimasinten lukumäärä, joka JOI:lla voi olla.

Esimerkkisyötteet ja -tulosteet

Esimerkkisyöte 1

5
OXXOX

Esimerkkituloste 1

2

JOI:n painamat merkit ovat vasemmalta lukien järjestyksessä: ympyrä, risti, risti, ympyrä, risti. Jos JOI:lla on ympyräleimasimia, ristileimasimia ja ympyrä-risti-leimasimia vastaavasti $0, 1, 2$ kappaletta, hän voi painaa merkit näin käyttämällä leimasimia seuraavassa järjestyksessä:

• Käytä $1$. ympyrä-risti-leimasinta ja paina ympyrä ja risti tässä järjestyksessä.
• Paina tämän oikealle puolelle $2$. ympyrä-risti-leimasimella risti ja ympyrä tässä järjestyksessä.
• Paina lopuksi tämän oikealle puolelle ristileimasimella risti.

Koska ei ole mahdollista, että hänellä olisi vähintään $3$ ympyrä-risti-leimasinta, tulostetaan $2$.

Esimerkkisyöte 2

14
OXOXOXOXXOXOXO

Esimerkkituloste 2

7

Esimerkkisyöte 3

10
OOOOOOOOOO

Esimerkkituloste 3

0