Acorn Sum Queries

You are given a tree with n branches, where each branch contains a certain number of acorns. The branches are numbered from 1 to n. You are also given q queries. Each query is represented by a pair of integers l_i and r_i. For each query, you need to calculate the total number of acorns in the branches from l_i to r_i (inclusive).

An efficient approach is to use prefix sums. Define the prefix sum array \(P\) as follows: \[ P[i] = \sum_{j=1}^{i} a_j, \] where \(a_j\) represents the number of acorns on branch \(j\). Then, the answer for a query (l, r) is given by: \[ P[r] - P[l-1]. \]

Implement this idea to answer all the queries efficiently.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer n, the number of branches.
• The second line contains n space-separated integers representing the number of acorns on each branch.
• The third line contains an integer q, the number of queries.
• The next q lines each contain two space-separated integers l and r representing the range of branches for that query.

outputFormat

For each query, output the sum of acorns in the specified range on a new line.

## sample

1
5
1
1 1

5

</p>