## SGIFT - Sabbir and gifts

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 

hide comments
 < Previous 1 2 Next > rifazn: 2018-01-26 16:54:08 I sorted using python's built in sort method that sorts in O(n logn), then I used binary search for finding the lower bound, then again for finding the upper bound. Doing a sum(lower-bound, upper-bound) makes the whole solution into O(n) which is maybe why I am getting a TLE. Is that what I am not doing right here? How can I do the sum in less than O(n) in this case? abhi1004: 2017-12-11 20:10:37 Time limit is too strict for JAVA . Complexity of my algorithm is (O(q*log(n))) still giving TLE. nadstratosfer: 2017-10-13 18:18:18 I hardly sympathize with the bloatware called Java but the time limit here does make it a I/O challenge. O((n+q)*logn) in Python TLEs unless the code looks like a golfing solution. This shouldn't be necessary for AC. testing java: 2017-09-11 15:13:07 What's the point of so strict time limit? I try to solve it in java, and because of time limits I do not know whether there is something wrong with algorithmic part of my code or I got TLE simply because my io isn't fast enough. It slightly spoils fun from solving problems Last edit: 2017-09-11 15:46:33 holmesherlock: 2017-05-27 13:24:20 thanx a ton buddy @vengatesh15 Shubham Jadhav: 2017-05-17 20:26:11 O(n^2) works holmesherlock: 2017-04-03 18:55:43 i guess my code is fine but it is giving runtime error ,:-( gogetgoogle: 2017-03-13 13:44:15 when blue.mary got wa , its the test cases , not him XD shahzada: 2017-03-04 11:18:59 Sabbir ,could you please tell me where i am getting wrong ? is there any problem in my algorithm or my approach. Last edit: 2017-03-04 17:32:41 vengatesh15: 2017-03-03 10:43:04 use long long that cost me 1 WA but an easy one:-)

 Added by: sabbir Date: 2017-02-26 Time limit: 0.400s-0.800s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All