题目描述

给定由 $n$ 个正整数组成的序列a~$1$~，a~$2$~，a~$3$~，⋯，a~n~和 $m$ 个区间[l~i~，r~i~]，分别求这 $m$ 个区间的区间和。

输入格式

第一行包含一个正整数 $n$，表示序列的长度 第二行包含 $n$ 个正整数a~$1$~，a~$2$~，a~$3$~，⋯，a~n~。(a~i~<=$10^4$^) 第三行包含一个正整数 $m$ 表示区间的数量 接下来 $m$ 行，每行包含两个正整数l~i~，r~i~，满足 $1<=l$~i~<=r~i~<=n。 $1<=n$,m<=$10^5$^。

输出格式

共 $m$ 行，每一行包含一个正整数，表示第 $i$ 组区间的答案。

样例

样例输入 1

4
4 3 2 1
2
1 4
2 3

样例输出 1

10
5