Range Sum Queries

You are given an array of n integers and q queries. Each query provides two integers L and R (1-indexed), and your task is to calculate the sum of the elements from index L to R (inclusive).

You can improve your solution by using a prefix sum array. The formula to compute the sum for any query is given by:

\( S = prefix[R] - prefix[L-1] \)

Make sure your program reads input from stdin and writes output to stdout.

inputFormat

The first line contains a single integer n, the number of elements in the array.

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

The third line contains a single integer q, the number of queries.

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

outputFormat

For each query, output a single line with the sum of the array elements from index L to R.

## sample

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

6
9
15

</p>