描述

给定一个整数数列，以及若干对数列位置，要求算出每一对位置的对应区间的子数列的和。例如，对于数列{8,4,35,-1}，区间[1, 3]的子数列和为4+35+(-1)=38。

输入输出格式

输入

第一行：一个正整数n，代表数列的项数

第二行：用空格隔开的n个整数，代表数列的每一项

第三行：一个整数m，代表需要查询的区间的数目

第四行到第m+3行：每一行有两个空格隔开的非负整数a和b，代表区间范围，a<=b。

输出

m+3行，每一行代表对应区间的子数列和。

样例

4
8 4 35 -1
3
1 3
2 2
0 2

38
35
47