Prefix Sum Queries

You are given an array of integers and a series of queries. Each query consists of two integers \(L\) and \(R\) (with 1-indexing) and asks you to compute the sum of the elements from index \(L\) to \(R\) (inclusive).

In order to solve this problem efficiently, you should first compute the prefix sums array \(prefix\) defined by:

\( prefix[i] = arr[1] + arr[2] + \dots + arr[i] \)

Then, the sum for a query \((L, R)\) can be computed as:

\( sum(L, R) = prefix[R] - prefix[L-1] \)

Process each query and output the result on a new line.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer (n), the number of elements in the array.
• The second line contains (n) space-separated integers representing the array.
• The third line contains an integer (q), the number of queries.
• Each of the following (q) lines contains two space-separated integers (L) and (R) representing a query.

outputFormat

For each query, output the sum of the subarray from index (L) to (R) (inclusive) on a separate line to standard output (stdout).## sample

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

6
9
15