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 gifts were attractive to sabbir. he wanted to buy all the gifts which are in price range    . 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 . 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 3rd line there will be Q number of queries.

next Q lines contain two integes a and b
 

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