A toll plaza keeps a ledger of n daily receipts, one integer per day (a negative value means net refunds outweighed receipts that day). You must answer q independent queries. Each query gives two day numbers l and r (1-indexed, inclusive) and asks for the total of all receipts from day l through day r.

Input format

Line 1: an integer n. Line 2: n space-separated integers, the daily receipts in day order. Line 3: an integer q. Next q lines: two integers l and r.

Output format

Print q lines. Line i is a single integer: the total receipts for query i, in the order the queries are given.

Constraints

• 1 <= n <= 100000
• 1 <= q <= 100000
• -1000000 <= each receipt <= 1000000
• 1 <= l <= r <= n

5
3 -1 4 1 5
2
1 3
2 5

6
9

4
7 7 7 7
1
1 4

28