Range Sum Query with Prefix Sum Array

You are given an array of integers and a series of queries. Each query asks you to compute the sum of a contiguous subarray defined by two indices l and r (0-indexed).

Your task is to implement an efficient solution using a prefix sum array. The prefix sum array P of an array A is defined as:

\( P[i] = \sum_{j=0}^{i-1} A[j] \) for \( i \geq 1 \) with \( P[0] = 0 \).

With the prefix sum array, the sum of elements between indices l and r (inclusive) can be computed as:

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

Implement the functions to construct the prefix sum array and answer multiple queries efficiently.

inputFormat

The input is read from standard input and is in the following format:

1. An integer n representing the number of elements in 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 l and r (0-indexed) representing a query.

outputFormat

For each query, output the sum of the array elements from index l to r (inclusive) on a new line. The output should be printed to standard output.

## sample

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

6
9
12

</p>