Prefix Sum Subarray Sum

You are given an array of n integers. Your task is to answer q queries, where each query asks for the sum of a subarray between two indices l and r (1-indexed).

To solve this problem efficiently, you should first preprocess the array by computing its prefix sums. The prefix sum array prefix is defined as:

\( prefix[i] = \sum_{j=1}^{i} a_j \)

Once you have the prefix sum array, the sum of the subarray from l to r can be computed as:

\( sum = prefix[r] - prefix[l-1] \)

Implement a solution that reads from stdin and outputs the results for each query to stdout.

inputFormat

The first line contains an integer n, the number of elements in the array. The second line contains n space-separated integers representing the elements of the array. The third line contains an integer q, the number of queries. Each of the following q lines contains two space-separated integers l and r, representing the left and right indices (1-indexed) of a subarray.

outputFormat

For each query, output a single line with the sum of the subarray from index l to r.## sample

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

6
9
15