Problems Statement

Given are NN intergers A1...ANA_1 ... A_N.
You will process QQ queries on this sequence.
In the ii-th query, given two itergers XiX_i and YiY_i, find the sum of AXi,AXi+1...AYiA_{X_i}, A_{X_i+1} ... A_{Y_i}.

Constraints

1N1051 \le N \le 10^5
1Ai1001 \le A_i \le 100
1Q2×1041 \le Q \le 2 \times 10^4
1XiYiN1 \le X_i \le Y_i \le N

Input

NN
A1ANA_1 \ldots A_N
QQ
X1 Y1X_1\ Y_1
\vdots
XQ YQX_Q\ Y_Q

Output

Print QQ lines.
The ii-th line should contain the response to the ii-th query.

Sample Input 1

5
1 4 6 1 7
3
2 5
4 4
1 3

Sample Output 1

18
1
11

Sample Input 2

10
3 2 6 9 2 8 9 4 4 3
4
1 10
6 8
6 8
1 10

Sample Output 2

50
21
21
50

Submit


Go (1.21)