说明

给定长度为 n 的数组 a，进行 m 次询问，每次询问区间 [L, R] 的元素之和。

输入格式

第一行一个整数 n，表示数组长度。
第二行 n 个整数 a[1], a[2], …, a[n]。
第三行一个整数 m，表示询问次数。
接下来 m 行，每行两个整数 L, R，表示询问区间（下标从 1 开始）。

输出格式

对于每次询问，输出一行一个整数，即区间 [L, R] 的和。

样例

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

-5
7
-3

数据范围

2 ≤ n, m ≤ 10000
1 ≤ L < R ≤ n
−1000 ≤ a[i] ≤ 1000