Given an immutable array of length n and q queries like “calculate the sum of an array subsegment from l to r ”. Print the answer for each request.
Input
The first line contains a number n – array size (\(1 <= n <= 10^5\)). The second line contains n &ndash numbers ; array elements. Modulo numbers do not exceed \(10^9\). The third line contains the number q – number of requests (\(1 <= q <= 10^5\)). Followed by q lines, each of which contains 2 numbers: l and r (\(1 <= l <= r <= n\)).
Output
Print the answers to all queries, each on a separate line.
Examples
| # |
Input |
Output |
| 1 |
5
1 2 3 4 5
3
1 2
3 3
2 5
|
3
3
14 |