maggu-and-queries

Maggu is very serious about his work. He is so bossy that everyone fears him.

One day he gave his assistant N records with a number r[i] written on each of them. He wanted his assistant to quickly fulfill his Q queries of sum of numbers written on the ith to jth records.
One query i j represents r[i] + r[i+1] + ..... + r[j-1] + r[j].
His assistant is very poor in calculations & fears that Maggu will fire her at failure, so she needs your programming skills to save her job.

INPUT:

First line will contain the number of records N.

Next line contains N integers r[i] denoting the number written on ith record.

Next line will contain the number of queries Q proposed by Maggu.

Next Q lines will contain a query of the form "i j"

OUTPUT:

For each query "i j", output the sum of numbers written on ith record to jth record on separate lines.

CONSTRAINTS:

1 ≤ N ≤ 10^6

1 ≤ r[i] ≤ 10^9

1 ≤ Q ≤ 10^6

1 ≤ i ≤ j ≤ N

SAMPLE INPUT
10
6 8 9 2 3 4 6 2 1 63
5
3 7
1 4
2 9
5 6
4 4

SAMPLE OUTPUT
24
25
35
7
2

Source: hackerearth | Difficulty: MEDIUM


Solutions: