Range Sum Queries

Suppose you have an array of integers such as 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Adding up all of its elements is easy. One loop is enough.

int size = 10;
int total = 0;
for (int i = 0; i < size; i += 1) {
    total = total + v[i];
}

To add up a different range of elements (positions 5 through 7, for example) you change only a few parts of the loop. In this problem you do that computation many times.

The first line contains the array size $n$. The second line contains the $n$ elements of the array, separated by spaces.

The line after the array contains the number of queries $m$. Each of the next $m$ lines holds one query, a pair of integers start and end. For that query you compute the sum of the elements from position start to position end.

Limits

• $1 \le n \le 100000$
• Positions are counted from 0. start and end are positions of the array and satisfy 0 <= start <= end <= n-1.
• The elements of the array are integers from 0 to 9.
• $1 \le m \le 10000$

For each query, print on its own line the sum of the elements from position start to position end. Both end positions belong to the sum.

That is, print array[start] + array[start+1] + ... + array[end-1] + array[end].