CSUMQ - Cumulative Sum Query

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

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!

hide comments
2021-03-22 20:53:53
i am a dumb
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.
2020-06-29 19:36:40
simple prefix sum question with some if else conditions :)
2020-06-19 17:59:08
Simple prefix sum problem. As the time constraint is very high brute force would work.
2020-06-06 19:00:19
use prefix sum
2020-04-28 10:27:54
It has a 7s limit, obviously, brute force would get accepted.
2019-08-02 14:54:35
even brute force approach is getting accepted
2019-05-25 07:47:22
Use segment trees, for any range queries.
2018-05-19 07:42:28
Dataset is very weak :/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.