Given an array
nintegers, you are asked to answer
qqueries. All the queries have the form: “What is the sum of elements in the array
[l; r]?” (both endpoints are inclusive and the indexing starts from 0). This time the number of queries and the size of the array are significantly larger. Can you think of a way to answer those queries faster?
The first line of the input contains a single integer
n- the number of elements in the array (1 ≤ n ≤ ). The next line contains
nintegers separated by a space, that represent the elements of the array .
The following line contains a single integer
q- the number of queries (1 ≤ q ≤ ). The next
qlines contain queries of the form
The program should print
qlines, each of which is the sum of elements in the array
8 1 2 3 4 5 6 7 8 3 0 4 5 6 5 7
15 13 21