题目描述

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

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

输入格式

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

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

4
2
2

说明/提示

对于 $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$。