eolymp
bolt
Try our new interface for solving problems
Problems

Sum on a segment

Sum on a segment

Time limit 1 second
Memory limit 128 MiB

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
Author В.Гольдштейн
Source 2010 Kharkiv, Winter Trainings, Day 2