Fruits Sum Queries

You are given a sequence of trees, each bearing a certain number of fruits. Your task is to answer several queries about the total number of fruits on a contiguous segment of trees.

We define a prefix sum array (P) such that (P[i] = \sum_{j=1}^{i} a_j), where (a_j) is the number of fruits on the (j^{th}) tree. For a query with indices (l) and (r) (1-based), the answer is calculated as (P[r] - P[l-1]).

inputFormat

The first line contains an integer (n), the number of trees.
The second line contains (n) space-separated integers representing the number of fruits on each tree.
The third line contains an integer (q), the number of queries.
The following (q) lines each contain two space-separated integers (l) and (r) (1-based indices) representing a query.

outputFormat

For each query, output a single integer on a new line --- the sum of fruits from tree (l) to tree (r).## sample

5
4 7 2 9 5
3
1 3
2 4
1 5

13
18
27