Range Sum Queries Using Prefix Sum

You are given an array of integers along with multiple queries. For each query, you need to compute the sum of the subarray starting from index \(l\) to index \(r\) (inclusive). To solve this problem efficiently, you should preprocess the array to construct a prefix sum array \(prefix\) defined as:

\( prefix[i] = \sum_{j=0}^{i-1} arr[j] \)

Then, the sum for a query \((l, r)\) can be computed in \(O(1)\) time using the formula:

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

This method is widely used in competitive programming to answer range sum queries quickly.

inputFormat

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

• The first line contains an integer \(n\) representing 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\) representing the number of queries.
• Each of the next \(q\) lines contains two space-separated integers \(l\) and \(r\) (0-indexed) representing a query, meaning you should determine the sum of the elements from \(l\) to \(r\) inclusive.

outputFormat

Output \(q\) lines. The \(i^{th}\) line should contain a single integer representing the sum of the subarray for the \(i^{th}\) query.

## sample

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

3
9
15

</p>