A8708 | Fence

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 $h_{i}$ . 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 $l_{1}$ to $r_{1}$ and from $l_{2}$ to $r_{2}$ 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<=r_{1}-l_{1})$ the following condition holds: $h_{l1+i}+h_{l2+i}=h_{l1}+h_{l2}$ .

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<=10^{5}$ ) — the number of wood planks in the fence. The second line contains $n$ space-separated integers $h_{1},h_{2},...,h_{n}$ ( $1<=h_{i}<=10^{9}$ ) — the heights of fence planks.

The third line contains integer $q$ ( $1<=q<=10^{5}$ ) — the number of queries. Next $q$ lines contain two space-separated integers $l_{i}$ and $r_{i}$ ( $1<=l_{i}<=r_{i}<=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.