2. Riadna naháňačka vzorové riešenie

Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zaťiaľ programovať nevieš, ale chcel/a by si vedieť možeš skúsiť náš python tutoriál.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Kodikovi na [email protected]

Jednej noci o polnoci mladí vedúci idú spať,
v tú chvíľu Adam zo svojej skrýše vylieza a šepká: “Budeme sa hrať.”
Odbyla polnoc,
dúfam, že nie ste unavení,
vyskočím na chodbu,
tak berte nohy na ramená.
Nato Dávid chytá nervy,
stojí na chodbe, sleduje Adama.
Adam v strachu nahlas skríkne : “Čo horšieho sa mi môže stať?”
Kubo z druhej strany vraví :“Dohral si sa kamarát.”
Adam sa klepe a kričí :“No tak musím ujsť!”
Dávid aj Kubo sa rozbehnú a idú ho chytiť.

Úloha

Máme \(n\) metrov chodby. Na každom metre chodby je buď Adam, Dávid alebo Kubo (z každého môže byť viac). Každý Dávid má práve jedného Kuba s ktorým chytá. Navyše platí, že keď si tieto dvojice predstavíme ako dvojice zátvoriek kde Dávid je ( a Kubo je ), tvoria správne uzátvorkovanú postupnosť na chodbe¹. Keď sa Dávid stretne s Kubom tak to obja vzdajú a idú spať, lebo im Adam ušiel. Dávid by chcel zistiť, koľko Adamov nedokážu chytiť, teda koľko je takých Adamov, ktorí sa nenachádzajú medzi žiadnou dvojicou Dávida a Kuba ktorí spolu chytajú.

Formát vstupu

Na prvom riadku je celé číslo \(n\) (\(1 \leq n \leq 1\,000\,000\)) udávajúce dĺžku chodby v metroch.
Na ďalšom riadku sa nachádza reťazec písmen “A”, “D”, a “K” dlhý \(n\) znakov – zápis chodby, kto kde stojí.

Formát výstupu

Na výstup vypíšte jedno celé číslo - počet Adamov, ktorých nechytia.

Hodnotenie a obmedzenia

Existujú 2 sady vstupov. Platia v nich nasledovné obmedzenia:

Príklady

Input:

9
DKDDDAKKK

Output:

0

Input:

10
DAAKADKAAA

Output:

4

Prví dvaja Adamovia sú obklúčení, ostatní nie su obklúčení.