Subarray Sum Queries

You are given an array of n integers. Your task is to answer m queries. Each query consists of two integers, L and R (1-indexed), and you need to output the sum of the subarray from L to R inclusive. To solve the problem efficiently, you can precompute a prefix sum array.

If the array is represented as \(a_1, a_2, \dots, a_n\), then the prefix sum array \(P\) is defined as:

\(P[i] = \sum_{j=1}^{i} a_j\) for \(1 \leq i \leq n\) with \(P[0]=0\). The sum for a query \((L, R)\) is \(P[R]-P[L-1]\).

Input is provided via standard input (stdin) and output should be printed to standard output (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 array.

The third line contains an integer m, the number of queries. The next m lines each contain two integers L and R (1-indexed) representing a query.

outputFormat

For each query, output the sum of the subarray from index L to R (inclusive) on a separate line.

## sample

8
3 7 2 6 5 8 1 9
4
1 4
2 6
3 8
1 8

18
28
31
41

</p>