Calculate Magic Values

You are given an integer N representing the number of elements in an array, and an array A of N integers. Each element represents a magic value. You are also given Q queries. Each query is defined by two integers, L and R (1-indexed), which represent the range within the array.

Your task is to compute the sum of the magic values for the subarray from index L to R (inclusive) for each query.

Mathematically, for a query with indices \(L\) and \(R\), you need to calculate:

\( S = \sum_{i=L}^{R} A[i] \)

It is recommended to use a prefix sum array to answer the queries efficiently.

inputFormat

The input is given in the following format:

1. The first line contains a single integer N, representing the number of elements in the array.
2. The second line contains N space-separated integers, denoting the array A.
3. The third line contains a single integer Q, representing the number of queries.
4. The next Q lines each contain two space-separated integers L and R (1-indexed) describing a query.

outputFormat

For each query, output a single integer on a new line representing the sum of the magic values in the subarray from index L to R (inclusive).

## sample

5
5 3 8 6 7
3
1 3
2 5
1 5

16
24
29

</p>