Sum Subarray Queries

You are given an array of n integers and q queries. Each query is described by two integers \(L\) and \(R\) (1-based indices) and asks to compute the sum of the subarray from index \(L\) to \(R\). In other words, for each query, you need to calculate:

[ S = \sum_{i=L}^{R} a_i ]

Your task is to process all queries and output the corresponding subarray sums. The input is provided via standard input (stdin) and the output must be printed to standard output (stdout).

inputFormat

The input is given in the following format:

n
a1 a2 a3 ... an
q
L1 R1
L2 R2
...
Lq Rq

Here, \(n\) is the number of elements in the array, followed by \(n\) space-separated integers representing the array. Then, \(q\) is the number of queries, followed by \(q\) lines each containing two integers \(L\) and \(R\) indicating the bounds (inclusive) of the subarray.

outputFormat

For each query, output the sum of the subarray specified by \(L\) and \(R\) on a new line.

## sample

5
1 2 3 4 5
1
1 3

6

</p>