flip01

Cerință

O operație de tipul flip pe un șir $a_1, a_2, \dots, a_N$, format doar din cifrele $0$ si $1$, se realizează prin efectuarea următorilor doi pași:

• Pasul 1: Se vor alege două numere naturale $l$, $r$, astfel încât $1 \leq l \leq r \leq N$
• Pasul 2: Pentru fiecare poziție $i$ din intervalul $[l, r]$, dacă $a_i$ este $0$, își va schimba valoarea în $1$, altfel își va schimba valoarea în $0$. (din $0$ în $1$ și din $1$ în $0$).

Se dau $N$, șirul $a_1, a_2, \dots, a_N$ și $Q$ interogări de forma $[st, dr]$:

Pentru fiecare interogare dată, trebuie sa aflați numărul minim de operații flip pe care trebuie să le facem, plecând de la șirul inițial, astfel încât pentru fiecare poziție $i$ din intervalul $[st, dr]$, $a_i$ este egal cu $0$.

Rezolvați această problemă și vă rasplătim cu $100$ de puncte! (sau, cu cât puteți...).

Operațiile efectuate la fiecare interogare NU se păstrează pentru interogările următoare (cu alte cuvinte, toate interogările pleacă de la șirul inițial).

Date de intrare

Pe prima linie a fișierului de intrare flip.in se va afla numărul $N$, reprezentând lungimea șirului, iar pe a doua linie șirul $a_1$, $a_2$, ..., $a_N$. Pe a treia linie a fișierului se va afla numărul $Q$, reprezentând numărul de interogări. Pe următoarele $Q$ linii se vor afla două numere $st$ și $dr$, care reprezintă capetele intervalului pentru care vrem să aflăm răspunsul la întrebarea din enunț.

Date de ieșire

Fișierul de ieșire flip.out va conține răspunsurile la cele $Q$ interogări pe linii separate, în ordinea în care au fost date.

Restricții și precizări

• $1 \leq N, Q \leq 2 \times 10^5$
• $a_i = \{ 0, 1 \}$
• Pentru fiecare interogare, $1 \leq st \leq dr \leq N$

Exemplul 1

flip.in

5
0 1 0 1 1
3
4 5
4 4
1 4

flip.out

1
1
2

Explicație

Pentru cea de-a treia interogare, va trebui să folosim operația flip pentru intervalele $[2, 2]$ respectiv $[4, 4]$.

Exemplul 2

flip.in

1
1
1 
1 1

flip.out

1