众所周知,狮均国内吼叫总值(Real GDS per lion)是衡量一个狮子国狮子健康程度的重要指标。
其计算方法为:选取若干个狮子,将每个狮子吼叫的次数相加即为总值。
叶子是狮子国健康委员会的会长,有人举报小林汇报的狮均国内吼叫总值的数据有误,所以他想请你帮忙计算。
具体来说,你会知道编号为 1 到 n 的 n 只狮子吼叫的次数 a_i 。
叶子会提出 q 个问题。对于每个问题他会给出 l 和 r 。
他想知道编号在 l 和 r 之间的狮子的狮均国内吼叫总值。
第一行,一个整数 n ,代表狮子的数量。
第二行, n 个整数 a_i ,代表编号为 i 的狮子的吼叫次数。
第三行,一个整数 q ,代表叶子的问题数。
接下来 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
30% 的数据: q=1 ;
100% 的数据: 1≤n≤10^6,1≤a_i≤10^3,1≤q≤2*10^5,1≤l≤r≤n 。