Prefix Sum Queries

This problem requires you to process multiple range sum queries on an array using the prefix sum technique. Given an array arr of integers and a set of queries, each query specifies two indices l and r (1-indexed), and your task is to compute the sum of the subarray from l to r. The solution utilizes the prefix sums array defined as:

\( P[i] = \sum_{j=1}^{i} arr[j] \) with \( P[0] = 0 \)

Then, the answer for a query from l to r is given by:

\( \text{sum}(l, r) = P[r] - P[l-1] \)

You need to read the input from stdin and output the answers to stdout, each on a new line.

inputFormat

The input is given in the following format:

n
arr[0] arr[1] ... arr[n-1]
q
l1 r1
l2 r2
...
lq rq

Where:

• n (1 ≤ n ≤ 10^5) is the number of elements in the array.
• arr[i] are the integer elements of the array.
• q is the number of queries.
• Each of the next q lines contains two integers l and r (1-indexed) representing the query range.

outputFormat

For each query, output a single line containing the sum of the subarray from index l to r.

## sample

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

6
9
15

</p>