UFPR14D - Inquire

(EN:)

Every tourist visiting our city must visit the May 4 avenue. There are N houses, numbered from 1 to N. There are Pi people living at house i.

The statistic institute is proceeding with the survey this year. They will make many queries about the avenue's population. For each query, two numbers A and B, with A <= B, are given. You must determine the total number of people living in all houses from house A to house B, inclusive.

Input

First line contains the number  N (1 <= N <= 105). Second line contains N integers P1, P2, ..., PN, indicating how many people live at each house (for each 1 <= i <= N, 0 <= Pi <= 100). Next line contains the integer Q (1 <= Q <= 104), the number of queries to be processed. Each of the next Q lines describes a query with two integers A and B (1 <= A <= B <= N).

Output

For each query, print a line with its result.

(PT-BR:)

Todo turista que visita a cidade deve conhecer a Avenida Quatro de Maio. Há N casas na avenida, numeradas sequencialmente de 1 a N. Há Pi pessoas morando na casa de número i da avenida.

O instituto de estatística está realizando o censo deste ano. Para tal, o instituto irá realizar diversas consultas sobre a população da avenida. Em cada consulta, são dados dois números A e B, com A <= B. Para cada consulta, é necessário determinar o número total de pessoas que moram entre as casas A e B, inclusive.

Sua tarefa é, dada a população de cada casa e as consultas que o instituto irá fazer, determinar a resposta para cada consulta dada.

Entrada

A primeira linha da entrada contém o inteiro N (1 <= N <= 105). A segunda linha contém N inteiros P1, P2, ..., PN, indicando a população de cada casa da avenida (Para cada 1 <= i <= N, 0 <= Pi <= 100). A terceira linha contém um inteiro Q (1 <= Q <= 104), indicando o número de consultas a serem realizadas. Por fim, cada uma das próximas Q linhas descreve uma consulta. Cada linha contém dois inteiros A e B (1 <= A <= B <= N).

Saida

Para cada consulta, imprima uma linha contendo sua resposta.

Example

Input:
4
10 2 8 72
3
4 4
1 3
2 4 Output: 72
20
82
Input:
5
1 2 3 4 5
2
1 5
1 1 Output: 15
1

Added by:Ricardo Oliveira [UFPR]
Date:2016-08-03
Time limit:0.5s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:14 Seletiva UFPR

hide comments
2017-11-23 09:03:08
Use large arrays to avoid overflow in testcases
2017-01-23 06:41:17
simple one..
2017-01-06 12:54:12
my 50th :)
2016-12-13 21:27:35
very easy problem...
gave 5 min to code and got 0.6 p :)
2016-09-10 00:37:30
guys,this question is very easy.....do in this way.....while taking scan for array store the sum in another array.....
2016-09-03 19:58:52
AC in one go..!
2016-08-15 20:44:45
.6 pts for this ques :P
2016-08-08 14:09:15
can someone give me link to the tutorial question??
2016-08-07 08:48:24 kataria
pappu que.
Should be moved tutorial
2016-08-06 19:13:07
is there a way to see the best solution for this problm?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.