Range Sum Queries

Medium#arrays #prefix-sums· solved by 0 · time limit 2.0 s

Answer $q$ queries: each asks for $a_l + a_{l+1} + \dots + a_r$ (1-based). Re-adding for every query is too slow — precompute prefix sums.

Input

$n$ , the $n$ integers, $q$ , then $q$ lines with $l$ and $r$ .

One sum per line.

$1 \le n, q \le 10^5$ , $|a_i| \le 10^6$

Input

Output

15
5
4