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.