UFPR14D - Inquire

no tags 

(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



hide comments
Sushovan Sen: 2016-08-04 19:27:42

Similar problem present in tutorial section.

sharath_111: 2016-08-04 16:48:49

Last edit: 2016-08-04 18:44:35
lalit_nit2: 2016-08-04 15:15:10

How people done it in 0.0s in C ...

Got it :)

Last edit: 2016-08-05 11:36:07
Vipul Srivastava: 2016-08-03 19:36:10

Tutorial.


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