D. Fence
time limit per test
3 seconds
memory limit per test
256 megabytes
standard input
standard output

John Doe has a crooked fence, consisting of n rectangular planks, lined up from the left to the right: the plank that goes i-th (1 ≤ i ≤ n) (from left to right) has width 1 and height hi. We will assume that the plank that goes i-th (1 ≤ i ≤ n) (from left to right) has index i.

A piece of the fence from l to r (1 ≤ l ≤ r ≤ n) is a sequence of planks of wood with indices from l to r inclusive, that is, planks with indices l, l + 1, ..., r. The width of the piece of the fence from l to r is value r - l + 1.

Two pieces of the fence from l1 to r1 and from l2 to r2 are called matching, if the following conditions hold:

  • the pieces do not intersect, that is, there isn't a single plank, such that it occurs in both pieces of the fence;
  • the pieces are of the same width;
  • for all i (0 ≤ i ≤ r1 - l1) the following condition holds: hl1 + i + hl2 + i = hl1 + hl2.

John chose a few pieces of the fence and now wants to know how many distinct matching pieces are for each of them. Two pieces of the fence are distinct if there is a plank, which belongs to one of them and does not belong to the other one.


The first line contains integer n (1 ≤ n ≤ 105) — the number of wood planks in the fence. The second line contains n space-separated integers h1, h2, ..., hn (1 ≤ hi ≤ 109) — the heights of fence planks.

The third line contains integer q (1 ≤ q ≤ 105) — the number of queries. Next q lines contain two space-separated integers li and ri (1 ≤ li ≤ ri ≤ n) — the boundaries of the i-th piece of the fence.


For each query on a single line print a single integer — the number of pieces of the fence that match the given one. Print the answers to the queries in the order, in which the queries are given in the input.

1 2 2 1 100 99 99 100 100 100
1 4
1 2
3 4
1 5
9 10
10 10