Есептің шарты

JOI-да $3$ түрлі мөрдің әрқайсысынан $0$ немесе одан көп дана бар: дөңгелек мөр, крест мөр және дөңгелек-крест мөр. Бұлар қағазға дөңгелек немесе крест белгілерін басып шығара алатын мөрлер.

Дөңгелек мөрді қолданғанда $1$ дөңгелек, ал крест мөрді қолданғанда $1$ крест басылады. Дөңгелек-крест мөрді қолданғанда көлденеңінен бір қатарға $1$ дөңгелек пен $1$ крест басылады, ал мөрдің бағытын өзгерту арқылы дөңгелектің оң жағына крест түсетіндей етіп те, кресттің оң жағына дөңгелек түсетіндей етіп те басуға болады.

JOI өзінде бар мөрлердің әрқайсысын лайықты ретпен дәл $1$ реттен қолданып, қағазға көлденеңінен бір қатарға дөңгелектер мен кресттерді басып шықты. Басылған дөңгелектер мен кресттер тізбегі $S$ жолымен беріледі. $S$ — O және X таңбаларынан тұратын ұзындығы $N$ жол; егер $S_i = $ O болса, бұл JOI басқан белгілердің сол жақтан санағанда $i$-шісі дөңгелек екенін, ал егер $S_i =$ X болса, оның крест екенін білдіреді ($1 \le i \le N$).

Сіз JOI-да қанша мөр бар екенін білмейсіз, бірақ оның басып шығарған дөңгелектер мен кресттер тізбегін білесіз. Басылған дөңгелектер мен кресттер тізбегі бойынша JOI-да болуы мүмкін дөңгелек-крест мөрлері санының ең үлкен мүмкін мәнін табыңыз.

Шектеулер

• $1 \le N \le 100000 (= 10^5)$
• $S$ — ұзындығы $N$ болатын жол.
• $S$ жолының әрбір таңбасы O немесе X.

Кіріс және шығыс

Кіріс
Кіріс деректер стандартты кірістен келесі форматта беріледі:
$N$
$S$

Шығыс
JOI-да болуы мүмкін дөңгелек-крест мөрлері санының ең үлкен мүмкін мәнін шығарыңыз.

Кіріс және шығыс мысалдары

Кіріс мысалы 1

5
OXXOX

Шығыс мысалы 1

2

JOI басып шығарған белгілер солдан оңға қарай ретімен: дөңгелек, крест, крест, дөңгелек, крест. Егер JOI-да сәйкесінше $0, 1, 2$ дөңгелек мөр, крест мөр және дөңгелек-крест мөр бар десек, мөрлерді келесі ретпен қолдану арқылы белгілерді дәл солай басып шығаруға болады:

• $1$-ші дөңгелек-крест мөрін қолданып, дөңгелек пен крестті осы ретпен басу.
• Оның оң жағына $2$-ші дөңгелек-крест мөрін қолданып, крест пен дөңгелекті осы ретпен басу.
• Соңында оның оң жағына крест мөрін қолданып, крестті басу.

Дөңгелек-крест мөрі $3$ немесе одан көп болуы мүмкін емес болғандықтан, $2$ шығарылады.

Кіріс мысалы 2

14
OXOXOXOXXOXOXO

Шығыс мысалы 2

7

Кіріс мысалы 3

10
OOOOOOOOOO

Шығыс мысалы 3

0