Given a series of numbers, e1, e2, e3, ..., eN.
With these numbers, we want to know what the sum is in some consecutive range.
In every testcase, you will be given M queries.
Each of them contains two integers which represent left bound (L) and right bound (R) respectively.
Your mission is to give the result of eL + eL+1 + ... + eR,
-
Hint 0 : If you get WA for testcase 1, sample input and output might help you.
Hint 1 : If you get TLE for next three testcases, you should think how to decrease some redundant operations for calculations. Try to store other useful information in the array, instead of sum up all the elements for every query! You may search for the problem's title: "prefix sum".
Hint 2 : If you get MLE, you have to reduce the size of array you created and decide what exactly should be in the array.
First line contains one integer N which is the size of elements.
Second line will have N integers representing all elements in the testcase.
Third line contains one integer M which is the number of queries.
For following M lines, each line contains exactly two integers that stand for left bound (L) and right bound (R) respectively.
It is guaranteed that:
1. 10 ≦ N ≦ 1,000,000
2. 0 ≦ ei ≦ 100,000, for 1 ≦ i ≦ N
3. L must be less than or equal to R, and R won't exceed the size of elements.
For each query, just give the answer in one line.
Also, remember to print '\n' in the end of line.