Problems
Sum on a segment
Sum on a segment
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 data
The first line contains the amount of numbers n~(1 \le n \le 10^6). The second line contains the numbers a_i~(1 \le a_i \le 1000). The third line contains the number of queries m~(1 \le m \le 10^6). Each of the next line contains the query l_i and r_i~(1 \le l_i \le r_i \le n).
Output data
Print in separate m lines the numbers S[l_i ... r_i].
Examples
Input example #1
5 1 2 3 4 5 5 1 5 2 3 3 4 2 5 1 4
Output example #1
15 5 7 14 10