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

akshayvenkat: 2017-02-28 08:42:59

Sabbir, could you tell me why my code is giving TLE? Is my algorithm inefficient?

Edit : Thank you Sabbir, Finally got AC. Great problem, please do edit off the spoiler comments so that the rest too can enjoy it!

Last edit: 2017-03-01 19:50:41
aman224: 2017-02-27 19:40:45

Thanks a lot :)

Last edit: 2017-02-28 03:57:05
itissabbir: 2017-02-27 17:46:28

@aman224 I have fixed the time limit for JAVA .

Last edit: 2017-02-27 23:23:22

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