Sum Zero

Roxy, the space traveler, is facing a very abstract problem. Since she’s clueless as to how to solve it, you, as her best friend, have no choice but to help her out:

She is given an array $c\_1, c\_2, \dots , c\_N$ consisting of $N$ integers, and $Q$ pairs of endpoints $(L\_i , R\_i)$, each representing the subarray $c\_{L\_i} , c\_{L\_i+1}, \dots , c\_{R\_i}$, where $1 ≤ i ≤ N$.

For each such pair $(L\_i , R\_i)$, Roxy is asked what is the maximum number of disjoint sum-0 subarrays one can choose from the queried array $c\_{L\_i} , c\_{L\_i+1}, \dots , c\_{R\_i}$. Two subarrays are considered disjoint if they have no entries in common; however, they can still have neighboring endpoints. Note that, there might be entries from the queried array that are not part of any of the chosen subarrays.

The first line of the input contains a single integer $N$.

The second line contains $N$ space-separated integers $c\_1, c\_2, \dots , c\_N$.

The third line contains the number $Q$ of queries.

The next $Q$ lines contain two numbers $L\_i$ and $R\_i$ each, representing the $i$th query.

Print $Q$ lines: on the $i$th line you should print the answer to the $i$th query.

• $1 ≤ N ≤ 400\\,000$
• $1 ≤ Q ≤ 400\\,000$
• $−10^9 ≤ c\_i ≤ 10^9$ for all $1 ≤ i ≤ N$
• $1 ≤ L\_i ≤ R\_i ≤ N$ for all $1 ≤ i ≤ Q$