You are a given an array of N elements.
Now you have to answer Q queries.
Each Query contains two integers L and R.
For each query you have to print sum of elements present in subarray A[L...R].

Input :
first line contains an integer 'N' (number of elements in array).
On next line there will be N integers (array elements).
on next line there is an integer Q (number of Queries)
Next Q lines contains two integers L and R.

output :
for each L R print the required output

constraint :
1<=N<=100000
1<=Q<=100000
1<=L<=R<=N
1<=a[i]<=1000000000