== include(page="template/taskheader" task_id="sumzero") ==
Roxy, călătoarea spaţială, se confruntă cu o problemă foarte abstractă. Întrucât nu are idee cum să o rezolve, tu, ca prieten al ei cel mai bun, trebuie să o ajuţi.

Ea primeşte un vector  c{~1~}, c{~2~}, ..., c{~N~} ce conţine $N$ numere întregi şi $Q$ perechi de puncte finale(L{~i~}, R{~i~}), fiecare reprezentând subvectorul , unde 1 &le i &le Q.

Ea primeşte un vector  c{~1~}, c{~2~}, ..., c{~N~} ce conţine $N$ numere întregi şi $Q$ perechi de puncte finale (L{~i~}, R{~i~}), fiecare reprezentând subsvectorul c{~L{~i~}~}, c{~L{~i~}+1~}, ...., c{~R{~i~}~}, unde 1 ≤ i ≤ Q.
Pentru fiecare pereche (L{~i~}, R{~i~}), Roxy este întrebată care este numărul maxim de subsecvenţe disjuncte de sumă $0$ pe care le poate alege din subvectorul c{~L{~i~}~}, c{~L{~i~}+1~}, ...., c{~R{~i~}~}. Două subsecveţe sunt considerate disjuncte dacă nu au elemente în comun; cu toate acestea, pot avea puncte finale învecinate. Reţineţi că pot exista elemente din vectorul interogat care nu fac parte din niciuna din subsecvenţele alese.

h2. Date de intrare

Fişierul de intrare $sumzero.in$ ...

Fişierul de intrare $sumzero.in$ conţine pe prima linie un singur număr întreg $N$.
A doua linie conţine $N$ numere separate prin spaţii c{~1~}, c{~2~}, ..., c{~N~}.
A treia linie conţine numărul de întrebări $Q$.
Următoarele $Q$ linii conţin câte două numere L{~i~} şi R{~i~}, reprezentând a i-a întrebare.

h2. Date de ieşire

În fişierul de ieşire $sumzero.out$ ...

În fişierul de ieşire $sumzero.out$ se vor afişa $Q$ linii, linia $i$ conţinând răspunsul la întrebarea cu numărul $i$.

h2. Restricţii

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 400 000$
* $1 ≤ Q ≤ 400 000$
* $-10^9^$ ≤ c{~i~} ≤ $10^9^$
* 1 ≤ L{~i~} ≤ R{~i~} ≤ N
* Pentru $20$ de puncte, $1 ≤ N, Q ≤ 5 000$
* Pentru alte $40$ de puncte, $1 ≤ N, Q ≤ 100 000$

h2. Exemplu
table(example). |_. sumzero.in |_. sumzero.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 10
  1 2 -3 0 1-4 3 2 -1 1
  3
  1 10
  1 5
  2 9
| 4
  2
  2

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="sumzero") ==