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 \le i \le n) (from left to right) has width 1 and height hi. We will assume that the plank that goes i-th (1 \le i \le n) (from left to right) has index i.

A piece of the fence from l to r (1 \le l \le r \le 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 \le i \le 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 \le n \le 105) - the number of wood planks in the fence. The second line contains n space-separated integers h1,h2,...,hn (1 \le hi \le 109) - the heights of fence planks.

The third line contains integer q (1 \le q \le 105) - the number of queries. Next q lines contain two space-separated integers li and ri (1 \le li \le ri \le 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.