Prefix Sum Range Queries

You are given an array of n integers. Your task is to preprocess the array by computing its prefix sums and then answer q queries efficiently. The prefix sum array P is defined by the relation: $$P[0]=0$$ and $$P[i]=P[i-1]+A[i-1]$$ for \(1 \le i \le n\), where \(A\) is the given array.

For each query, you are provided two integers \(l\) and \(r\) (1-indexed) and must calculate the sum of the elements from index \(l\) to \(r\), inclusive. This problem tests your ability to preprocess data for fast range sum queries.

inputFormat

The input is read from stdin and is structured as follows:

• 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 elements.
• The third line contains a single integer q, the number of queries.
• Each of the following q lines contains two space-separated integers, l and r (1-indexed), describing a query.

outputFormat

For each query, output a single line to stdout containing the sum of the elements from index l to r inclusive.

## sample

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

6
9
15

</p>