【深进1.例1】求区间和

题目描述

给定由 $n$ 个正整数组成的序列 $a_1, a_2, \cdots, a_n$ 和 $m$ 个区间 $[l_i,r_i]$，分别求这 $m$ 个区间的区间和。

输入格式

第一行包含一个正整数 $n$，表示序列的长度。

第二行包含 $n$ 个正整数 $a_1,a_2, \cdots ,a_n$。

第三行包含一个正整数 $m$，表示区间的数量。

接下来 $m$ 行，每行包含两个正整数 $l_i,r_i$，满足 $1\le l_i\le r_i\le n$。

输出格式

共 $m$ 行，其中第 $i$ 行包含一个正整数，表示第 $i$ 组答案的询问。

输入样例 #1

4
4 3 2 1
2
1 4
2 3

输出样例 #1

10
5

说明/提示

样例解释

第 $1$ 到第 $4$ 个数加起来和为 $10$。第 $2$ 个数到第 $3$ 个数加起来和为 $5$。

输入样例 #2

1
1
1
1 1

输出样例 #2

1

输入样例 #3

45
764 3807 6742 5248 21 4738 1136 5564 5385 2033 8295 1923 6513 211 7543 9266 6218 7735 4586 8016 9976 2200 1098 3798 7256 9572 409 8698 595 4928 4344 6253 2942 9489 39 9829 8200 6013 4804 3822 9517 836 4764 1737 9623
31
36 41
2 40
28 28
39 44
17 40
26 29
31 42
39 40
25 30
23 31
9 12
26 40
28 35
6 38
28 44
12 37
23 25
36 37
40 43
5 14
13 42
2 16
34 45
25 32
21 21
42 45
13 16
3 15
20 22
44 44
19 38

输出样例 #3

42185
199245
8698
25480
130820
19274
66088
8626
31458
40698
17636
79937
37288
174801
86810
141637
12152
18029
18939
35819
164706
68425
68673
42055
9976
16960
23533
55352
20192
1737
108241

数据范围

对于 $50 \%$ 的数据：$n,m\le 1000$；

对于 $100 \%$ 的数据：$1 \le n, m\le 10^5$，$1 \le a_i\le 10^4$。