Prefix Sum Queries

You are given an array of n integers and are required to perform several range sum queries efficiently. First, compute the prefix sum array where each element \(S_i\) is defined as \(S_i = \sum_{j=1}^{i} a_j\). For each query, given two indices L and R, output the sum of the subarray from index L to R (inclusive).

Note: The prefix sum array satisfies the formula \(S_i = S_{i-1} + a_i\) for \(i \geq 2\), with \(S_1 = a_1\).

inputFormat

The first line contains an integer n representing the size of the array.

The second line contains n space-separated integers representing the elements of the array.

The third line contains an integer q representing the number of queries.

Each of the next q lines contains two space-separated integers L and R (1-indexed), indicating the bounds of the query.

outputFormat

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

## sample

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

6
9
15

</p>