Description

  一次偶然的机会,Haibara得到了一粒APTX4869毒药。为了研究其成分以制作解药,Haibara在显微镜下对APTX4869进行了详细的观察。APTX4869的分子结构是一条链,链上的每个部位宽窄不一,形成了锯齿的形状。Haibara在这条分子链上选择了N个具有代表性的节点,并用一个整数表示每个节点处的宽度。
  APTX4869进入活生物体后,分子链将会在体内环境下带动机能细胞一起折叠、扭曲,引起生物体各系统的紊乱而致死。但在特殊的情况下,APTX4869的分子链重叠时,部分锯齿刚好整齐地“咬合”在一起,避免了紊乱的发生,却造成了生物体细胞全面变小或恢复为以前某时刻的状态。我们说APTX4869分子链的n个代表节点中,第lara个节点与lbrb个节点是“咬合”的,当且仅当节点区间[la,ra],[lb,rb]满足下列条件:
  1.[la,ra]与[lb,rb]不重叠,即la ≤ ra < lb ≤ rb或lb ≤ rb < la ≤ ra;
  2.[la,ra]与[lb,rb]的长度相等,即ra-la = rb-lb;
  3.对应节点的高度和相等,即对于任意的0 ≤ i ≤ ra - la,有w[la+i]+w[lb+i]=w[la]+w[lb],其中w[x]表示第x (1 ≤x ≤n) 个节点处的宽度。
  现在Haibara给出m段区间,请你帮她统计一下对于每段区间,有多少段区间与它是“咬合”的。

Input

  第一行一个整数n。
  第二行包含n个整数,第i个数表示w[i],即第i个节点处的宽度。
  第三行一个整数m。
  接下来m行,每行有两个整数l,r,表示询问有多少段区间与[l,r]是“咬合”的。

Output

  对每个询问输出一个整数表示答案。

Sample Input
10
1 2 2 1 100 99 99 100 100 100
6
1 4
1 2
3 4
1 5
9 10
10 10
Sample Output
1
2
2
0
2
9
Hint

数据范围与约定
  对于20%的数据,1&lt;=n,m&lt;=1001&lt;=n,m&lt;=100
  对于另30%的数据,询问区间的长度不超过 1010
  对于100%的数据,1&lt;=n,m&lt;=1000001&lt;=w[i]&lt;=1091&lt;=l&lt;=r&lt;=n1&lt;=n,m&lt;=100000,1&lt;=w[i]&lt;=10^9,1&lt;=l&lt;=r&lt;=n