Subarray Sum Queries Using Prefix Sums

In this problem, you are given an array of integers and you need to answer multiple queries on the sum of subarrays. A query is specified by two indices ( l ) and ( r ) (1-indexed) and requires you to compute the sum ( \sum_{i=l}^{r} a_i ). To answer the queries efficiently, you should precompute the prefix sums array ( P ) defined as follows: [ P[i] = \sum_{j=1}^{i} a_j, \quad \text{for } 1 \le i \le n, \quad \text{and } P[0]=0. ] Then, the sum for a query ( (l, r) ) can be computed as: [ \text{sum}(l, r) = P[r] - P[l-1]. ] Your task is to implement a solution that reads input from standard input and writes the answer for each query to standard output.

inputFormat

The input is given from standard input in 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 elements ( a_1, a_2, \dots, a_n ).
• The third line contains an integer ( m ), the number of queries.
• Each of the next ( m ) lines contains two integers ( l ) and ( r ) (1-indexed), representing a query for the sum of the subarray from index ( l ) to index ( r ).

outputFormat

For each query, output a single line containing the sum of the subarray for the corresponding query.## sample

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

6
9
15