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 \leq i \leq N$.

Task

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.

Input

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.

Output

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

Constraints

• $1 \leq N \leq 400 \ 000$
• $1 \leq Q \leq 400 \ 000$
• $-10^9 \leq c_i \leq 10^9$ for all $1 \leq i \leq N$
• $1 \leq L_i \leq R_i \leq N$ for all $1 \leq i \leq Q$

Examples

stdin

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

stdout

4
2
2