Barry Kripke has given Sheldon a problem, which he says is a "Very easy widdle". In the problem, there is an array of integers of length N and Q queries, each asking to calculate the number of continuous subarrays which are having their least element in the range of [L, R].

Formally speaking, for each query, calculate the total number of subarrays such that for each of those subarrays following condition is satisfied,

$L \leq min(A_i, A_{i+1}, A_{i+2}, ..., A_j) \leq R$

for a subarray from indices i to j.

Since, Sheldon is busy writing his Nobel prize speech, he has given you the task of solving the problem.

Input Format:

First line contains N, length of the array.

Second line contains N integers denoting the given array.

Third line contains Q, number of queries.

Each of the next Q lines contains L and R denoting the query.

Output Format:

For each query, print the required answer in separate line.

Constraints:

$1 \leq N \leq 10^6$

$1 \leq A_i \leq 10^9$

$1 \leq Q \leq 10^5$

$1 \leq L \leq R \leq 10^9$