Sum on a segment

Input

The first line contains the number of elements $n$ $(1 \leq n \leq 1 0^{6})$ (1 \le n \le 10^6). The second line contains the numbers $a_{i}$ a_i $(1 \leq a_{i} \leq 1000)$ (1 \le a_i \le 1000) separated by spaces. The third line contains the number of queries $m$ $(1 \leq m \leq 1 0^{6})$ (1 \le m \le 10^6). Each of the next $m$ lines contains the indices $l_{i}$ l_i and $r_{i}$ r_i $(1 \leq l_{i} \leq r_{i} \leq n)$ (1 \le l_i \le r_i \le n).

Output

Print the value $S_{l_{i}, r_{i}}$ S_{l_i, r_i} for each query on a separate line.

Examples

Example 1

Loading