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