题目描述 题目译自 Romanian Master of Informatics $2020$ Day$2$ T$2$ 「Sum Zero」

宇宙探险家 Roxy 遇到了一道棘手的数学难题，身为她最好的朋友，你必须帮她解决。

给定一个包含 $N$ 个整数的数组 $c_1, c_2, \ldots , c_N$，以及 $Q$ 个查询，每个查询包含一对左右端点 $(L_i, R_i)$，表示数组 $c_{L_i}, c_{L_{i+1}}, \ldots , c_{R_i}$。

对于每个查询 $(L_i, R_i)$，你需要找出在这个子数组中，最多能选出多少个和为 $0$ 的不相交子数组。两个子数组不相交是指它们没有共同的元素，但可以相邻。注意，子数组中的一些元素可能不属于任何选出的子数组。

输入格式 第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $c_1, c_2, \ldots , c_N$。

第三行包含一个整数 $Q$，表示查询的数量。

接下来 $Q$ 行，每行包含两个整数 $L_i$ 和 $R_i$，表示一个查询。

输出格式 输出 $Q$ 行，每行输出一个整数，表示对应查询的答案。

样例

输入

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

输出

4
2
2

数据范围与提示 对于所有输入数据，满足：

• $1 \leq N \leq 4\cdot 10^5$
• $1 \leq Q \leq 4\cdot 10^5$
• 对于所有 $1 \leq i \leq N$，$-10^{9} \leq c_{i} \leq 10^{9}$
• 对于所有 $1 \leq i \leq Q$，$1 \leq L_{i} \leq R_{i} \leq N$

详细子任务附加限制及分值如下表所示。