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    . 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
 

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
 

hide comments
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:-)

dwij28: 2017-03-01 09:09:28

O(n*log(n) + q*log(n)) is an accepted solution :)

itissabbir: 2017-02-28 19:44:03

Akshay Venkataramani, your query function is not running in log(n)


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