e-olymp
Problems

Sum on a segment

Sum on a segment

Given array of integers a1, ..., an. For given indexes l and r find

prb682.gif

Input

The first line contains the amount of numbers n (1n106). Second line contains the numbers ai (1ai1000) space separated. Third line contains the number of queries m (1m106). Each of the next line contains the query li and ri (1lirin).

Output

Print in separate m lines the numbers Sli..ri.

Time limit 1 seconds
Memory limit 128 MiB
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