Subarray Sum after Minimum Subtraction

You are given an array of n non-negative integers. Your task is to process several queries on this array.

Each query gives you two indices i and j (0-indexed) and defines a subarray from index i to j inclusive. For each query, subtract the minimum element in the subarray from every element in that subarray, and then compute and output the sum of the resulting values.

Formally, let the subarray be A[i..j] and let m = min(A[i], A[i+1], ..., A[j]). Then, the result is given by
\[ S(A, i, j) = \sum_{k=i}^{j} (A[k] - m) \]

You are required to answer all queries and output the results.

inputFormat

The input is given in the following format:

n
a1 a2 ... an
q
i1 j1
i2 j2
... 
iq jq

Here, the first line contains the integer n, the number of elements in the array. The second line contains n space-separated integers representing the array elements. The third line contains an integer q, the number of queries. Each of the next q lines contains two integers i and j representing a query, where 0 ≤ i ≤ j < n.

outputFormat

For each query, output a single integer on a new line, which is the computed sum after subtracting the minimum element of the corresponding subarray from each element.

## sample

6
1 2 3 1 2 3
3
0 1
1 4
2 5

1
4
5

</p>