Range Sum Query - Immutable

You are given an integer array (nums) of size (n). Your task is to process a series of queries where each query consists of two integers (i) and (j) (with (0 \leq i \leq j < n)). For each query, compute the sum of the elements of the array from index (i) to index (j) (both inclusive).

To achieve constant time query performance, you can precompute a prefix sum array (P) such that

(P[k] = \sum_{t=0}^{k-1} nums[t]) for (1 \leq k \leq n), with (P[0] = 0). Then the answer for a query ((i, j)) is given by:

(SUM(i, j) = P[j+1] - P[i]).

This problem is a classic example of using prefix sums to optimize range queries.

inputFormat

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

• The first line contains an integer \(n\), the number of elements in the array.
• The second line contains \(n\) space-separated integers, representing the array \(nums\).
• The third line contains an integer \(q\), the number of queries.
• Each of the next \(q\) lines contains two space-separated integers \(i\) and \(j\) (with \(0 \leq i \leq j < n\)) representing a query.

outputFormat

For each query, output a single line to standard output (stdout) that contains the sum of the elements of (nums) between indices (i) and (j) (inclusive).## sample

6
-2 0 3 -5 2 -1
3
0 2
2 5
0 5

1
-1
-3