== 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 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.

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 c{~L{~i~}~}, c{~L{~i~}+1~}, ...., c{~R{~i~}~}, unde 1 ≤ i ≤ Q.

h2. Date de intrare

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.

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

h2. Date de ieşire

Î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$.

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

h2. Restrictii

h2. Restricţii

* $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 |

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

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

|

h3. Explicaţie
 
...

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