题目描述

给出 $n$ 个整数 $a_1,a_2,\cdots,a_n$，接受 $m$ 次询问，每次询问第 $i \sim j$ 个数的和。

请使用 $O(n)$ 的递推方法预处理（前缀和），并以 $O(1)$ 的效率处理每次询问。

输入格式

第 1 行，1 个正整数 $n$。

第 2 行，$n$ 个用单个空格隔开的整数 $a_1,a_2,\cdots,a_n$。

第 3 行，1 个正整数 $m$。

之后 $m$ 行，每行 2 个用单个空格隔开的整数 $i,j$，表示询问第 $i \sim j$ 个数的和。

输出格式

$m$ 行，依次为每次询问的结果。

数据范围

$1 \le n,m \le 10^6$；

$1 \le i \le j \le n$；

$-1000 \le a_1,a_2,\cdots,a_n \le 1000$。

样例

输入样例 1

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

输出样例 1

12
7
12