2. Lakťovaná

Po tom čo ľudia skolonizovali vesmír, začalo obdobie nudy, ale že brutálnej nudy. Jeden z dôsledkov tejto nudy bol aj nový šport, ale že brutálny šport. Lakťovaná. Pravidlá sú jednoduché (ale že brutálne): je niekoľko tímov s jeden alebo viac hráčmi, hráči sa postavia na rovnú čiaru a ak existuje nejaká dvojica ľudí, ktorí stoja vedľa seba a sú z rôznych tímov, tak sa navzájom ulakťujú (naraz sa ulakťuje stále len jedna dvojica). Toto sa opakuje, až kým sa nemá kto lakťovať. Keďže počet ľudí nie je nekonečný, chceli by sme vás poprosiť, aby ste naprogramovali program, ktorý vypočíta, koľko minimálne ľudí ostane živých, na základe ich počiatočného postavenia.

Úloha

Na prvom riadku vstupu dostanete číslo \(n\), počet hráčov. Na druhom riadku vstupu dostanete reťazec pozostávajúci z malých písmen anglickej abecedy dĺžky \(n\). V každom ťahu môžete eliminovať nejakú dvojicu susedných písmen, ktoré sú rozdielne. Aký najkratší reťazec vie vzniknúť po odstránení takýchto dvojíc ?

Formát vstupu

Na prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 10^6\)) udávajúce počet hráčov Na druhom riadku vstupu je postupnosť malých písmen anglickej abecedy reprezentujúca postavenie daných hráčov.

Máme štyri sady, každá je po 2 body, pre dané sady platia nasledovné obmedzenia:

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo určujúce minimálny počet ľudí, ktorí po skončení hry prežijú.

Príklady

Input:

3
sss

Output:

3

V prvom príklade sa nemá kto ulakťovať.

Input:

5
aabba

Output:

1

V druhom príklade sa najprv ulakťujú hráči na predposlednej a poslednej pozícii, teda ostane \(aab\). Následne sa ulakťujú hráči na predposlednej a poslednej pozícii a ostane \(a\).

Input:

6
aaazzz

Output:

0