== 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. Restricţii