Verkefnalýsing

JOI á $0$ eða fleiri af hverri af $3$ tegundum stimpla: hringstimpla, krossstimpla og hring-kross-stimpla. Þetta eru stimplar sem geta stimplað hring- eða krossmerki á blað.

Þegar hringstimpill er notaður stimplast $1$ hringur og þegar krossstimpill er notaður stimplast $1$ kross. Þegar hring-kross-stimpill er notaður stimplast $1$ hringur og $1$ kross í láréttri röð, og með því að snúa stimplinum er hægt að stimpla annaðhvort þannig að krossinn sé hægra megin við hringinn eða þannig að hringurinn sé hægra megin við krossinn.

JOI notaði hvern stimpil sem hann átti nákvæmlega $1$ sinni í viðeigandi röð og stimplaði hringi og krossa í lárétta röð á blað. Röðin af stimpluðum hringjum og krossum er táknuð með strengnum $S$. $S$ er strengur af lengd $N$ sem samanstendur af O og X; ef $S_i = $ O þýðir það að $i$-ta merkið frá vinstri af þeim sem JOI stimplaði sé hringur, og ef $S_i =$ X þýðir það að það sé kross ($1 \le i \le N$).

Þú veist ekki hversu marga stimpla JOI á, en þú þekkir röðina af hringjum og krossum sem JOI stimplaði. Út frá röðinni af stimpluðum hringjum og krossum skaltu finna mesta mögulega fjölda hring-kross-stimpla sem JOI gæti átt.

Skorður

• $1 \le N \le 100000 (= 10^5)$
• $S$ er strengur af lengd $N$.
• Hver stafur í $S$ er O eða X.

Inntak / Úttak

Inntak
Inntakið er gefið úr staðalinntaki á eftirfarandi sniði:
$N$
$S$

Úttak
Prentið mesta mögulega fjölda hring-kross-stimpla sem JOI gæti átt.

Dæmi um inntak / úttak

Dæmi um inntak 1

5
OXXOX

Dæmi um úttak 1

2

Merkin sem JOI stimplaði eru, í röð frá vinstri: hringur, kross, kross, hringur, kross. Ef JOI á $0, 1, 2$ hringstimpla, krossstimpla og hring-kross-stimpla í þessari röð getur hann stimplað merkin svona með því að nota stimplana í eftirfarandi röð:

• Nota $1$. hring-kross-stimpilinn til að stimpla hring og kross í þessari röð.
• Hægra megin við það, nota $2$. hring-kross-stimpilinn til að stimpla kross og hring í þessari röð.
• Að lokum, hægra megin við það, nota krossstimpilinn til að stimpla kross.

Þar sem ómögulegt er að hann eigi $3$ eða fleiri hring-kross-stimpla er prentað $2$.

Dæmi um inntak 2

14
OXOXOXOXXOXOXO

Dæmi um úttak 2

7

Dæmi um inntak 3

10
OOOOOOOOOO

Dæmi um úttak 3

0