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

Poveste şi cerinţă...

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") ==