Sums on subsegments
Problem
Implement a data structure to efficiently calculate the sums of consecutive array elements.
Input
The first line contains one natural number N (1 ≤ N ≤ 100000) — the number of numbers in the array.
The second line contains N numbers from 1 to 100000 — array elements.
The third line contains one natural number K (1 ≤ K ≤ 30000) — the number of requests to calculate the amount.
The next K lines contain two numbers — the numbers of the left and right elements of the array segment (it is assumed that the elements of the array are numbered from one).'
Imprint
For each query print the sum of the numbers of the corresponding section of the array. Print the numbers in one line separated by a space.
| Input |
Output |
5
4 4 8 7 8
2
1 2
1 3
| 8 16 |