Prefix Sum and Range Sum Query

You are given an array of integers and a number of queries. Each query asks for the sum of a subarray defined by two indices L and R (1-indexed). You need to compute the sum efficiently using prefix sums.

The prefix sum array \(P\) is defined as:

\[ P[i] = a_1 + a_2 + \cdots + a_i, \quad \text{for } 1 \le i \le n, \quad \text{and } P[0]=0. \]

Then, the sum of elements from index L to R is given by:

\[ \text{sum} = P[R] - P[L-1]. \]

Your task is to implement this logic, read input from stdin, and output each query result to stdout on a new line.

inputFormat

The input is read from standard input:

1. The first line contains a single integer \(n\) denoting the number of elements in the array.
2. The second line contains \(n\) space-separated integers representing the array.
3. The third line contains a single integer \(q\) denoting the number of queries.
4. Each of the following \(q\) lines contains two space-separated integers \(L\) and \(R\) (1-indexed), representing a query.

outputFormat

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

## sample

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

6
9
15

</p>