A paint seller sells paint like any ordinary paint seller but what makes him different is his collection of paints. He has a lot of different colors from which costumers can choose from. Another different thing about him is that he sells color in sets, like if a person chooses colors with index 1000 and 2000 then seller will charge him for all color with index greater than 1000 and less than equal to 2000.
Make a program for him to calculate the purchase made by every costumer so that he can make bills easily.
INPUT FORMAT :
- First line of input will contain an integer P, denoting the
number of different paints.
- Next line will contain an integer array C where Ci
= cost of paint with i-index.
- Next line will contain integer B which denotes bill to be made
for B different costumers.
- Following B lines will contain two integers F and L, which denotes index of first paint and index of last paint respectively.
OUTPUT FORMAT :
Your output should contain B lines, printing the purchase made by each costumer.
CONSTRAINTS :
1≤ P ≤105
1≤ Ci ≤105
1≤ B ≤105
1≤ F,L ≤105
all values follows 1-based index.
There are 5 different paint and three different costumers in given sample input.
For first costumer, total purchase = 2+3 = 5
For second costumer, total purchase = 3+4 = 7
For third costumer, total purchase = 3+4+5 = 12
