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 the gifts were attractive to Sabbir. He wanted to buy all the gifts which are in price range a <= p <= 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, the number of gifts in the shop.

In the next line there will be n integers p1, p2, p3 ... pn denoting price of every gift.

In the third line there will be Q, the number of queries.

The next Q lines contain two integers a and b.

Constraints

1 <= n <= 105.

1 <= pi <= 109.

1 <= Q <= 105.

1 <= a, b <= 109.

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