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