Prefix Sum Query

You are given an array of integers representing the impact values of segments. You are also given several queries; each query is a pair of integers \(l\) and \(r\) (1-based indices) that represents a range of segments. Your task is to compute, for each query, the sum of the impact values in the specified range.

To solve this problem efficiently, you should first precompute the prefix sums of the array. The prefix sum array \(P\) is defined as follows:

[ P[0] = 0 \quad \text{and} \quad P[i] = \sum_{j=1}^{i} impact_j \text{ for } i \ge 1, ]

Then, the sum for a query with indices \(l\) and \(r\) can be computed in constant time using the formula:

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

Make sure to read from standard input and write to standard output.

inputFormat

The input is given in the following format:

• The first line contains an integer \(n\), the number of segments.
• The second line contains \(n\) space-separated integers representing the impact values.
• The third line contains an integer \(q\), the number of queries.
• The following \(q\) lines each contain two integers \(l\) and \(r\), representing the left and right indices of a query (1-based).

outputFormat

For each query, output a single line containing one integer: the sum of the impact values from segment \(l\) to segment \(r\) (inclusive).

## sample

5
1 -2 3 10 -5
3
1 3
2 5
1 5

2
6
7

</p>