Sum of Elements between k-th Smallest Elements

You are given an array of n distinct integers and q queries. For each query, you are given two integers k₁ and k₂. Your task is to compute the sum of the elements between the k₁-th smallest and the k₂-th smallest elements in the array (inclusive). In other words, if the sorted array is \(a_{(1)}, a_{(2)}, \dots, a_{(n)}\), then for each query, you need to calculate

[ S = \sum_{i=k_1}^{k_2} a_{(i)} ]

Print each result on a new line.

inputFormat

The input is given from stdin and has the following format:

1. The first line contains a positive integer n, which is the number of elements in the array.
2. The second line contains n distinct integers separated by spaces.
3. The third line contains a positive integer q, the number of queries.
4. The next q lines each contain two integers k₁ and k₂ separated by a space.

outputFormat

For each query, output the sum of elements between the k₁-th smallest and the k₂-th smallest elements in the sorted array. Each answer should be printed on a new line.

## sample

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

14
6

</p>