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*_{*l*_{1} + *i*} + *h*_{*l*_{2} + *i*} = *h*_{*l*_{1}} + *h*_{*l*_{2}}$.

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.

Input

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.

Output

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.