1. Kopa kopania

Cisár Vespazián poveril staviteľa Oryctolaga veľkou úlohou: postaviť najväčší amfiteáter na svete.

Na veľkom amfiteátri je veľa roboty. Na začiatok treba, napríklad, pripraviť veľkú, rovnú stavebnú plochu. Ako na potvoru je však jediná veľká voľná plocha v okolí nerovná. Preto neostáva nič iné, ako ju umelo vyrovnať.

Na stavebnej ploche sú dva druhy nerovností, kopce a jamy, všetky rovnako veľké. Ak je teda nejaký kopec vedľa jamy, dá sa ich oboch veľmi jednoducho zbaviť – hlinou z kopca zasypeme jamu. Nie pri každom kopci je však jama, preto sa Oryctolagus bojí, že mu na konci nejaké nerovnosti zostanú.

Oryctolagus bude, samozrejme, jamy zasypávať najlepším možným spôsobom (teda tak, aby mu na konci zostalo čo najmenej nerovností). Zaujímalo by ho, koľko nerovností mu na konci zostane. Keďže sa mu to nechce počítať, zveril túto robotu svojej pravej ruke, Angelice. Tá to zasa zverila vám. A vy, ak budete šikovní, to môžete zveriť svojmu počítaču.

Úloha

Pre jednoduchosť budeme v tejto úlohe predpokladať, že svet je dvojrozmerný (má iba výšku a šírku) a stavebný pozemok má pôdorys v tvare úsečky. Pozdĺž tejto úsečky je niekoľko nerovností (jám a kopcov). Počet týchto nerovností aj ich poradie dostanete na vstupe. Máme povolené robiť nasledovnú operáciu:

• Ak medzi nejakou jamou a kopcom nie je žiadna iná nerovnosť (jama ani kopec), môžeme dať zasypať jamu hlinou z kopca. Daná jama aj kopec pri tom zaniknú.

Zistite, koľko nerovností nám ostane, ak pomocou tejto operácie odstránime najviac jám a kopcov, ako sa dá.

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(n\) (\(1 \leq n \leq 200\,000\)) – počet nerovností.

Na druhom riadku sa nachádza reťazec núl a jednotiek dlhý \(n\). Tento reťazec popisuje nerovnosti v poradí od začiatku po koniec pozemku: nuly znamenajú jamy a jednotky znamenajú kopce.

Formát výstupu

Na jediný riadok výstupu vypíšte najmenší možný počet nerovností, ktoré na konci zostanú.

Príklady

Input:

4
1100

Output:

0

Najprv zasypeme ľavú jamu hlinou z pravého kopca. To nám otvorí cestu, aby sme zasypali druhú jamu hlinou zo zostávajúceho kopca.

Input:

5
01010

Output:

1

Jedným z možných postupov je:

Input:

6
111111

Output:

6

V tomto prípade sa nedá vyrovnať nič.