Description

给出一组数列，求其中某区间的和，本是一件简单的事情。但这对于大聪明琪露诺来说却并不简单。琪露诺虽然会算区间的和，但她很快会忘记计算的结果，而琪露诺有需要多次计算区间和，用以完成问题。所以她请你编写一个程序，帮助她快速计算区间和，使她能更快地完成任务。

Format

Input

第一行一个数字 n，表示数组的长度。

第二行包括 n 个整数，每个整数之间用空格隔开，表示数组的数据。

第三行一个数字 m，表示琪露诺的询问次数。

从第四行开始到m+3行，每行包括两个数据L和R，表示询问的区间。

Output

一共 m 行，每行一个整数，表示对应的区间元素和。

Samples

10
5 2 -3 1 -5 10 150 300 1200 93
4
1 3
2 5
1 8
1 10

4
-5
460
1753

Limitation

1s, 1024KiB for each test case.