Range Sum Queries

Statement

The first line contains n, the second line contains n integers. The third line contains the number of queries q. Each of the next q lines contains l and r (1 ≤ l ≤ r ≤ n). For every query print the sum of the elements from a_l to a_r on its own line.

Examples

5
1 2 3 4 5
3
1 3
2 5
3 3

6
14
3

3
-1 -2 -3
2
1 3
2 2

-6
-2

Constraints

• 1 ≤ n, q ≤ 10^5
• -10^9 ≤ a_i ≤ 10^9