Sum on a segment

Very easy

Execution time limit is 2 seconds

Runtime memory usage limit is 128 megabytes

Given array of integers $a_{1}, ..., a_{n}$ . For given indexes $l$ and $r$ find

S_{l, r} = a_{l} + a_{l + 1} + ... + a_{r}

Input

The first line contains the amount of numbers $n (1 \leq n \leq 1 0^{6})$ . The second line contains the numbers $a_{i} (1 \leq a_{i} \leq 1000)$ . The third line contains the number of queries $m (1 \leq m \leq 1 0^{6})$ . Each of the next line contains the query $l_{i}$ and $r_{i} (1 \leq l_{i} \leq r_{i} \leq n)$ .

Output

Print in separate $m$ lines the numbers $S [l_{i} ... r_{i}]$ .

Examples

Input #1

Answer #1

Submissions 8K

Acceptance rate 25%