Efficient Range Sum Queries using Prefix Sums

You are given an array of n integers and q queries. For each query, you are required to calculate the sum of a subarray from index L to R (inclusive). To answer these queries efficiently, you will first build a prefix sums array.

The prefix sum array P is defined as:

\( P[0] = 0 \) and \( P[i] = P[i-1] + arr[i-1] \) for \( 1 \leq i \leq n \).

The sum for a query with indices \( L \) and \( R \) can then be computed as:

\( sum = P[R+1] - P[L] \).

Implement a program that reads the array and queries from standard input (stdin), processes the queries using the prefix sums technique, and writes the results to standard output (stdout).

inputFormat

The first line contains an integer n representing the number of elements in the array.

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

The third line contains an integer q representing the number of queries.

Each of the following q lines contains two space-separated integers, L and R, specifying the range (inclusive) of the subarray whose sum is to be computed.

outputFormat

For each query, output the sum of the subarray from index L to R (inclusive) on a new line.

## sample

6
1 2 3 4 5 6
3
0 2
1 3
2 5

6
9
18

</p>