61. Range Sum Queries

Challenge1000 ms256 MBSolved by 0%

You are given an array, then a number of queries q, then q lines each holding two 1-based indices l and r.

For each query, print the sum of elements from position l to position r inclusive, one answer per line.

Input ``` n a[1] a[2] ... a[n] q l r l r ... ```

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `1 ≤ l ≤ r ≤ n` - `-1000000 ≤ a[i] ≤ 1000000`

Input

The first line contains an integer n. The second line contains n space-separated integers. The third line contains an integer q, the number of queries. Each of the next q lines contains two integers l and r, a 1-based inclusive range.

Output

Print one integer per query, each on its own line, the sum of that range.

Input5 1 2 3 4 5 3 1 3 2 4 1 5

Output6 9 15

Notehas three overlapping ranges

Input5 1 2 3 4 5 1 3 3

Output3

Noteis a single-element range where l equals r

Hints

Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.

Hint 1Where to start

Hint 2The approachOpen hint 1 first. This one carries on from it.

Hint 3PseudocodeOpen hint 2 first. This one carries on from it.