Maggu and Queries

3.8

10 votes
Medium
Problem

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

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?