Sabbir is a little boy. he went to a gift shop with his mother. There were n different types of gifts in the shop. All the gifts were attractive to Sabbir. He wanted to buy all the gifts which are in price range a <= p <= b. You are given prices of all the gifts and a, b. Sabbir's mother need your help. Please calculate the total amount of price of all gifts of that range for Sabbir's mother.

Input

In the first line there will be n, the number of gifts in the shop.

In the next line there will be n integers p₁, p₂, p₃ ... p_n denoting price of every gift.

In the third line there will be Q, the number of queries.

The next Q lines contain two integers a and b.

Constraints

1 <= n <= 10⁵.

1 <= p_i <= 10⁹.

1 <= Q <= 10⁵.

1 <= a, b <= 10⁹.

Output

Print Q lines. Every line contains one integer, sum of all prices for that range given in the query.

Example

Input:
7
1 3 2 1 5 2 2
4
1 2
1 5
3 5
4 5

Output:
8
16
8
5

NOTE: for first query, Sabbir will buy all the gifts of prices 1, 2, 1, 2, 2. So, sum is 8.

For second query, Sabbir will buy all the gifts, so the sum is 16.