Range Sum Queries

You are given an array of integers and several queries. Each query asks for the sum of a subarray using 1-indexed positions. For a given query (x, y), you need to compute the sum of elements from index x to index y (inclusive).

The problem can be solved efficiently using prefix sums. In particular, if we define the prefix sum array (P) by
[ P[i] = \sum_{j=1}^{i} a_j, ]
with (P[0] = 0), then the sum for a query ((x,y)) can be computed as (P[y] - P[x-1]).

inputFormat

The input is given via standard input in the following format:

1. An integer (n) representing the size of the array.
2. (n) space-separated integers representing the array elements.
3. An integer (q) representing the number of queries.
4. (q) lines follow, each containing two integers (x) and (y) (1-indexed) indicating the start and end indices of a query.

outputFormat

For each query, output the sum of the subarray from index (x) to index (y) (inclusive) on a new line. The output should be via standard output.## sample

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

6
9
15