no tags

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  $a&space;\leq&space;p&space;\leq&space;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 . number of gifts in the shop.
in the next line there will be integers p1, p2 , p3 ... pn   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

$1&space;\leq&space;n&space;\leq&space;10^{5}$

$1&space;\leq&space;a,b&space;\leq&space;10^{9}$

### Output

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

### Example

Input:
71 3 2 1 5 2 241 21 53 54 5

Output:
81685NOTE: for first query sabbir will buy all the gifts of prices 1 , 2 , 1 , 2, 2 . so, sum is 8for second query sabbir will buy all the gifts . so the sum is 16