Olimpijada
Little Brojko is master at calculating sums of many numbers fast. Over last few months he trained so hard for today's Bosnian Summation Olympiad that now he is completely exhausted and can't even add 2 and 2. Therefore he asked his twin brother, Stojko, to go to the Olympiad instead of him. As Stojko isn't very good at sums he asked you to write him a program he could run on his pocket pc.
InputIn the first row of the input there is a natural number N ( 1 \leq N \leq 200 000 ). In the next row there are N integers greater than -10 000 and less than 10 000, separated with a space. In the next row there is a natural number Q ( 1 \leq Q \leq 200 000 ) and in the next Q rows each there is a pair of natural numbers A and B ( 1 \leq A \leq B \leq N ).
OutputFor each pair A and B write, in a separate row, sum of all numbers from Ath to Bth.
Input
Output
6
1 2 3 4 5 6
2
1 6
3 5Output
21
12Input
Output
6
3 -2 4 5 -7 4
2
2 5
3 6Output
0
6Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.