Sum Range Query

You are given an array of n integers and q queries. Each query consists of two integers l and r (1-based indexing), and your task is to compute the sum of elements from index l to index r inclusive.

To accomplish this efficiently, you are encouraged to use prefix sums. The prefix sum array P is defined as:

$$ P[i] = \sum_{j=1}^{i} a_j $$

Then, the sum of the subarray from l to r can be computed as:

$$ S = P[r] - P[l-1] $$

Make sure to handle large inputs efficiently.

inputFormat

The input is given via stdin in the following format:

• The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of elements in the array.
• The second line contains n space-separated integers representing the array elements. Each integer may be large (up to 10⁹).
• The third line contains an integer q (1 ≤ q ≤ 10⁵), the number of queries.
• Each of the following q lines contains two space-separated integers l and r (1 ≤ l ≤ r ≤ n), representing a query.

outputFormat

For each query, output the sum of the subarray from l to r (inclusive) on a new line to stdout.

## sample

5
1 2 3 4 5
1
1 3

6