Bridges

Architect Marijonas wants to improve transportation in an area where mountains are lined up in a straight line. The area is described by an array $A$ of size $N$, where $A[k]$ is the height of the $k$-th mountain.

Marijonas plans to build a bridge between two mountains. He has not yet decided which two, but he wants to know the construction cost of a bridge between mountains $L_i$ and $R_i$.

The cost is computed as follows.

• The bridge height $M_i$ is the average of the two end heights, rounded down: $M_i = \left\lfloor \frac{A[L_i] + A[R_i]}{2} \right\rfloor$
• The bridge passes over every mountain $k_i$ with $L_i \le k_i \le R_i$.
• If $A[k_i] \le M_i$, scaffolding must be built, and the cost is $M_i - A[k_i]$.
• If $A[k_i] > M_i$, a tunnel must be dug, and the cost is $1$.

Marijonas can compute the cost of one bridge easily, but he wants the costs for $Q$ pairs of mountains. Compute the construction cost for each query.

The first line contains the array size $N$. The second line contains the space-separated integers $A[1], A[2], \dots, A[N]$. The third line contains the number of queries $Q$. Each of the next $Q$ lines contains two space-separated integers $L_i$ and $R_i$.

Print $Q$ lines. Each line contains one integer, the construction cost of a bridge between mountains $L_i$ and $R_i$, in the same order as the queries.

• $1 \le N, Q \le 100\,000$
• $1 \le L_i \le R_i \le N$ ($1 \le i \le Q$)
• $1 \le A[i] \le 10\,000$ ($1 \le i \le N$)