(EN:)

Every tourist visiting our city must visit the May 4 avenue. There are N houses, numbered from 1 to N. There are P_i 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 <= 10⁵). Second line contains N integers P₁, P₂, ..., P_N, indicating how many people live at each house (for each 1 <= i <= N, 0 <= P_i <= 100). Next line contains the integer Q (1 <= Q <= 10⁴), 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á P_i 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 <= 10⁵). A segunda linha contém N inteiros P₁, P₂, ..., P_N, indicando a população de cada casa da avenida (Para cada 1 <= i <= N, 0 <= P_i <= 100). A terceira linha contém um inteiro Q (1 <= Q <= 10⁴), 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