说明

众所周知，狮均国内吼叫总值（Real GDS per lion）是衡量一个狮均国狮子健康程度的重要指标。

其计算方法为：选取若干个狮子，将每个狮子吼叫的次数相加即为总值。

叶子是狮均国健康委员会的会长，有人举报小林汇报的狮均国内吼叫总值的数据有误，所以他想请你帮忙计算。

具体来说，你会知道编号为 1 到 $n$ 的$n$ 只狮子吼叫的次数 $a_i$。

叶子会提出 $q$个问题。对于每个问题他会给出$l$ 和$r$。

他想知道编号在$l$ 和 $r$ 之间的狮子的狮均国内吼叫总值。

输入格式

第一行一个整数$n$，代表狮子的数量。

第二行 $n$ 个整数$a_i$，代表编号为 $i$的狮子的吼叫次数。

第三行一个整数 $q$，代表叶子的问题数。

第四到第$3+q$ 行，每行两个整数$l,r$。

输出格式

$q$行整数，代表计算出来的狮均国内吼叫总值

样例

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

4
10
3
8
15

数据范围

100% 的数据: $1≤n≤10^6,1≤a_i≤10^3,1≤q≤10^5,1≤l≤r≤n$。