just-press-the-button

Cerință

Se dă un șir binar, $S$, de lungime $N$. Avem la dispoziție următoarea operație: Alegem $i$ ($0 \leq i < N$) și dăm flip elementului $S_i$. Prin operația de flip, întelegem înlocuirea lui $1$ cu $0$ și invers.

Să se determine numărul minim de operații necesare astfel încât șirul $S$ să conțină cel puțin o subsecvență$^{\dag}$ de lungime pară care admite element majoritar.

Spunem că un element este majoritar într-un șir dacă acesta apare de mai multe ori decât restul elementelor la un loc.

Date de intrare

Pe prima linie se găsește numărul $N$. Pe a doua linie se găsește șirul $S$.

Date de ieșire

Se va afișa un singur număr, reprezentând numărul minim de operații necesare pentru a obține cel puțin un subșir contiguu de lungime pară care adminte element majoritar.

Restricții și precizări

• $2 \leq N \leq 200 \ 000$;
• $^{\dag}$ Prin subsecvență a unui șir se înțelege o succesiune de elemente aflate pe poziții consecutive în șirul inițial. De exemplu, pentru șirul $[1, 2, 3, 6, 12]$, $[1, 2]$ este o subsecvență, $[2, 3, 6]$ este o subsecvență, dar $[2, 6, 12]$ nu este.
• Pentru teste în valoare de $31$ de puncte, $1 \leq N \leq 200$;

Exemplul 1

stdin

3
101

stdout

1

Explicație

Putem aplica operația de flip pe primul element și obținem șirul $001$. Acum, primele două elemente formează o subsecvență cu elementul majoritar $0$.

Exemplul 2

stdin

6
000100

stdout

0

Explicație

Observăm că ultimele două elemente din șir formează o subsecvență de lungime pară care îl are pe $0$ ca element majoritar.