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
rameshwar409: 2024-07-27 11:19:27

haha

li0n_mmn: 2023-11-09 20:05:26

Note: i, j or indices in the query is not sorted I mean there are some cases where i>j
so, while using prefix sum swap(i,j) if(i>j)

anikpodder: 2023-05-03 08:50:47

I solved it with the prefix sum.

code_3r_: 2022-02-01 10:06:28

using simple prefix sum

mojoalpha: 2022-01-14 18:47:07

Using a segment tree could be a great choice too, in case you need more than one solution for this question

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

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!