In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of November 22nd
(this exercise will still be available for submission after that deadline, but without counting towards your grade)
[to understand the context of this problem, you should read the class #06 exercise sheet]

In this problem you should read your input from stdin using the input() function and you should print the requested output.

[IP061] Wallet Watcher

Penny has decided to finally get her finances under control (after a few too many Cheesecake Factory shifts and online shopping sprees).

She's written down the list of her last n money operations. Positive numbers represent money earned, and negative numbers represent money spent (usually on shoes or Thai takeout).

Now, Penny wants to answer several questions like: "How much money did I make (or lose) between operations a and day b?". The amount of money can be obtained by summing all the operations between positions a and b (inclusive).

The Problem

Write a program that receives a list of n integers m₁, m₂, ..., m_n where m_i represents the money earned or spent in operation i, and a list of q queries in the form of two integers a and b, and for each query prints the sum of all operations between a and b inclusive, that is, \( \sum\limits_{i = a}^b {m_i} \)

Input

The first line of input contains an integer n, the number of operations.

The second line contains n integers m₁, m₂, ..., m_n separated by a single space, the money earned or spent in each operation.

The third line contains an integer q representing the number of queries that follow

The next q lines each contain two integers a b representing that we want the summation of m_a, m_a+1, ..., m_b

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

NOTE: the limits are high and you must have an efficient solution.
If your code in each query simply iterates through positions a and b and sums, it will result in a Time Limit Exceeded.

10
100 -50 200 300 -150 400 -300 100 200 50
5
2 6
1 10
7 7
4 8
3 9

700
850
-300
350
750

Explanation of the input

• 1st query: sum = 700 | [-50, 200, 300, -150, 400]
• 2nd query: sum = 850 | [100, -50, 200, 300, -150, 400, -300, 100, 200, 50]
• 3rd query: sum = -300 | [-300]
• 4th query: sum = 350 | [300, -150, 400, -300, 100]
• 5th query: sum = 750 | [200, 300, -150, 400, -300, 100, 200]