太空旅行者 Roxy 遇到了一个非常抽象的问题。由于她不知道如何解决，作为她最好的朋友，你别无选择，只能帮助她：

给定一个包含 $N$ 个整数的数组 $c_1, c_2, \dots, c_N$，以及 $Q$ 对端点 $(L_i, R_i)$，每一对端点代表一个子数组 $c_{L_i}, c_{L_i+1}, \dots, c_{R_i}$，其中 $1 \le i \le N$。

对于每一对 $(L_i, R_i)$，Roxy 想知道在查询的子数组 $c_{L_i}, c_{L_i+1}, \dots, c_{R_i}$ 中，最多可以选择多少个互不相交且和为 0 的子数组。如果两个子数组没有公共元素，则称它们是不相交的；然而，它们可以有相邻的端点。注意，查询的子数组中可能存在不属于任何所选子数组的元素。

输入格式

第一行包含一个整数 $N$。 第二行包含 $N$ 个空格分隔的整数 $c_1, c_2, \dots, c_N$。 第三行包含查询的数量 $Q$。 接下来的 $Q$ 行，每行包含两个数字 $L_i$ 和 $R_i$，代表第 $i$ 次查询。

输出格式

输出 $Q$ 行：第 $i$ 行应输出第 $i$ 次查询的答案。

数据范围

• $1 \le N \le 400\,000$
• $1 \le Q \le 400\,000$
• $-10^9 \le c_i \le 10^9$，对于所有 $1 \le i \le N$
• $1 \le L_i \le R_i \le N$，对于所有 $1 \le i \le Q$

子任务

• 子任务 1（22 分）：$1 \le N \le 5\,000$，$1 \le Q \le 5\,000$
• 子任务 2（39 分）：$1 \le N \le 100\,000$，$1 \le Q \le 100\,000$
• 子任务 3（39 分）：无额外限制。

样例

样例输入 1

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

样例输出 1

4
2
2