Efficient Range Sum Queries on a Scoreboard

You are given an array of scores. Your task is to answer multiple queries where each query asks for the sum of scores between indices start and end (inclusive). To achieve this efficiently, you are required to precompute prefix sums.

Let \(A\) be the input array with \(n\) elements. Define the prefix sum array \(P\) of size \(n+1\) such that:

[ P[0] = 0, \quad P[i+1] = P[i] + A[i] \quad \text{for } i=0,1,\dots,n-1 ]

Then, for any query with indices start and end, the result is:

[ \text{result} = P[end+1] - P[start] ]

This approach ensures that each range sum query can be answered in \(O(1)\) time after an \(O(n)\) preprocessing step.

inputFormat

The first line contains a single integer \(n\) representing the number of scores. The second line contains \(n\) space-separated integers representing the scores array. The third line contains a single integer \(q\), the number of queries. Each of the next \(q\) lines contains two space-separated integers \(start\) and \(end\) representing a query (0-indexed).

outputFormat

For each query, output a single line containing the sum of the scores from index start to end (inclusive).

## sample

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

6
9
15

</p>