题目背景

译自 8th Romanian Master of Informatics, RMI 2020 D2T1。$\texttt{0.6s,\textcolor{red}{20M}}$。

请注意本题非同寻常的空间限制。

题目描述

给定长度为 $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$ 行，每行一个整数表示答案。

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

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