Prefix Sums and Subarray Queries

You are given an array of N integers and Q queries. Each query consists of two integers l and r (1-indexed) and asks you to compute the sum of the subarray from l to r.

You can efficiently answer these queries using prefix sums. The prefix sum array P is defined as:

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

Then the sum of the subarray from index l to r can be computed by:

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

For example, if arr = [1,2,3,4,5] and the query is (1,3), the answer would be 6 because \(1+2+3=6\).

inputFormat

The first line of the input contains an integer N, the number of elements in the array.

The second line contains N space-separated integers representing the array elements.

The third line contains an integer Q, the number of queries.

Each of the following Q lines contains two integers l and r (1-indexed) representing the query.

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>