Acorn Collection

Sam the Squirrel is on a mission to gather as many acorns as possible in preparation for the winter. The acorns are distributed across n trees. You are given an array a of length n where a[i] denotes the number of acorns on the i-th tree. Sam has m queries, and each query asks for the total number of acorns collected between two trees indexed from l to r (both inclusive).

Your task is to answer each query efficiently. A hint to solve this problem is to use prefix sums, which allow you to precompute cumulative totals and then answer any interval sum query in constant time.

Formally, after constructing the prefix sums array, the sum for any interval from l to r can be computed as:

\( \text{sum}_{l}^{r} = P[r] - P[l-1] \)

where \( P[i] = \sum_{j=1}^{i} a[j] \) and the indices follow 1-based indexing.

inputFormat

The first line of input contains a single integer n (\(1 \le n \le 10^5\)), representing the number of trees.

The second line contains n integers, where the i-th integer represents the number of acorns on the i-th tree.

The third line contains a single integer m (\(1 \le m \le 10^5\)), representing the number of queries.

Each of the following m lines contains two integers l and r (\(1 \le l \le r \le n\)), representing a query asking for the sum of acorns from the l-th tree to the r-th tree.

outputFormat

For each query, output a single line containing the sum of acorns between the specified indices (inclusive).

## sample

5
1 3 4 8 6
3
1 3
2 5
3 4

8
21
12

</p>