Sales between two days

Problem

A shop records its sales for n days. For several questions, report the total sales from day l to day r, both included. Days are numbered from 1.

Input: Line 1: n. Line 2: n integers (a day can be negative after refunds). Line 3: q. Then q lines, each with l and r.
Output: One total per question, one per line.
Constraints: 1 ≤ n, q ≤ 10^5
-10^4 ≤ sales ≤ 10^4
1 ≤ l ≤ r ≤ n

Example 1

Input

Output

6
9

Totals 6 and 9.

Example 2

Input

Output

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

Hint 1

Add the sales up once, keeping the running total after each day.

Hint 2

A range total is one running total minus another.

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