Range sum queries

Problem

A shop records its sales for n days, numbered from 0. For each query, print the total sales from day l to day r, both days included.

Input: The first line has n. The second line has n integers. The third line has q. Each of the next q lines has two integers l and r.
Output: q lines, each with the sum for one query.
Constraints: 1 ≤ n ≤ 2000
1 ≤ q ≤ 2000
-1000 ≤ each sale ≤ 1000
0 ≤ l ≤ r < n

Example

Input

Output

8
11

Items 0 to 2 add to 8. Items 1 to 4 add to 11.

Try the problem first. Open one hint at a time.

Hint 1

Adding the range for every query repeats work. Build the running totals once.

Hint 2

With a leading 0, the answer is prefix[r + 1] - prefix[l].

Write your Python code, run it on the examples and submit it to hidden tests.