As always, this time again, Suresh and Ramesh went to the tailor for shortening of their father's Pent. And guess what after a bite of Perk they went insane and got it shorten more then what was expected!

This time, Suresh's father wanted to punish him so that he will be busy for sometime, this way Suresh and Ramesh won't do anything wrong.

So he gave Suresh an array, A, of integers with N integers. And he will ask Q queries of form "L R", Suresh will have to calculate sum of array element from index L to R. And print it in a newline. Array is 1-based indexed.

Suresh want you to help in that.

Input:

First line containing N, array size

Second line with N space-separated integers A[1] A[2] ....... A[N].

Third line with an integer Q, the number of queries.

Then Q lines with two integers L R.

Output:

Print answer to each query in Q lines.

Constraints:

0 < L <= R< N<= 100001

0 < Q < 100001

-1001 < A[i] < 1001