CSUMQ - Cumulative Sum Query

no tags 

William Macfarlane wants to look at an array.

You are given a list of numbers and queries. Each query is specified by two numbers and j; the answer to each query is the sum of every number between the range [i, j] (inclusive).

Note: the query ranges are specified using 0-based indexing.

Input

The first line contains N, the number of integers in our list (N <= 100,000). The next line holds N numbers that are guaranteed to fit inside an integer. Following the list is a number (Q <= 10,000). The next Q lines each contain two numbers i and which specify a query you must answer (0 <= i, j <= N-1).

Output

For each query, output the answer to that query on its own line in the order the queries were made.

Example

Input:
3
1 4 1
3
1 1
1 2
0 2
Output:
4
5
6

hide comments
sourav_halder: 2021-06-16 16:47:34

use partial sum

eager_to_code: 2021-06-16 16:14:44

is there any discussion tab?

shreyasz_07: 2021-06-13 14:52:53

use kruskal algorithm

sandy5823: 2021-05-30 00:20:28

Striver

sugam10: 2021-04-28 06:57:37

use prefix sum

Last edit: 2021-04-28 06:58:19
mazharul_sub: 2021-03-22 20:53:53

i am a dumb

linhthebest: 2021-02-23 03:09:18

I´m a faggot.

Last edit: 2021-02-23 10:52:10
nitish_verma26: 2021-02-01 14:18:29

Sparse table is best suited for these type of questions where original array is not changing. One should go for this.

adikrmishra_1: 2020-06-29 19:36:40

simple prefix sum question with some if else conditions :)

shanto09: 2020-06-19 17:59:08

Simple prefix sum problem. As the time constraint is very high brute force would work.


Added by:Joshua Kirstein
Date:2014-10-27
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Hi Mom!