Range Sum Queries

You are given an array of n integers and m queries. For each query, you are given two integers, L and R, and you need to compute the sum of the subarray starting at index L and ending at index R (both inclusive).

You can solve this problem efficiently by precomputing the prefix sum array. The prefix sum array P is defined as:

\(P[i] = \sum_{j=1}^{i} a_j\)

Once the prefix sums are computed, the sum for any query (L, R) can be calculated as:

\(\text{sum} = P[R] - P[L-1]\)

Indices are 1-indexed.

inputFormat

The first line contains a single integer n, the number of elements in the array.

The second line contains n space-separated integers, the elements of the array.

The third line contains a single integer m, the number of queries.

Each of the following m lines contains two space-separated integers L and R representing a query.

outputFormat

For each query, output the sum of the elements in the range [L, R] on a new line.

## sample

5
1 2 3 4 5
3
1 3
2 4
1 5

6
9
15

</p>