题目描述

给出一个n个数组成的数组a[1],a[2],…,a[n]。你需要处理Q次询问，每次询问包含两个正整数l,r(1≤l≤r≤n)，对每个询问，你需要回答和式a[l]+a[l+1]+…+a[r]的值。

输入格式

第1行，1个正整数n。

第2行，n个整数a[1],a[2],…,a[n]，以空格分隔。

第3行，1个正整数Q。

接下来Q行，每行两个正整数l,r。

输出格式

输出Q行，第i行输出第i次询问的答案。

输入样例 #1

5
6 9 4 9 -8
3
2 3
4 4
3 4

输出样例 #1

13
9
13

输入样例 #2

6
1 -6 5 -4 2 4
3
1 6
2 5
3 6

输出样例 #2

2
-3
7

输入样例 #3

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

输出样例 #3

0
0
0
0

数据范围与约定

n,Q≤10⁵；-1000≤a[i]≤1000；1≤l≤r≤n；