Description

给定长度为 $N$ 的数列 $c_1,\cdots,c_N$。

$Q$ 次询问给定 $L,R$，求出最多能够选出多少个 $[L,R]$ 的不交子区间，满足每个子区间内 $c_i$ 的和均为 $0$。

Input Format

第一行，一个正整数 $N$。

第二行，$N$ 个整数 $c_1,\cdots,c_N$。

第三行，一个正整数 $Q$。

接下来 $Q$ 行，每行两个正整数 $L,R$。

Output Format

输出 $Q$ 行，每行一个整数表示答案。

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

4
2
2

Hint

对于 $100\%$ 的数据，保证：

• $1\le N,Q\le 4\times 10^5$；
• $-10^9\le c_i\le 10^9$；
• $1\le L\le R\le N$。