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₁ to r₁ and from l₂ to r₂ 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₁-l₁) 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⁵) − the number of wood planks in the fence. The second line contains n space-separated integers h₁,h₂,...,h_n (1≤h_i≤10⁹) − the heights of fence planks.

The third line contains integer q (1≤q≤10⁵) − 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.