Аналитик получил данные о продажах за n последовательных дней. Для каждого дня известно целое число — итоговые продажи за этот день.

После этого поступает q запросов от менеджеров. В каждом запросе указаны два числа l и r — границы периода, нумерация дней ведётся с единицы. Для каждого запроса требуется определить суммарные продажи за все дни от l до r включительно.

Необходимо ответить на все запросы.

Входные данные

В первой строке задано число n (1 <= n <= 2 * 10^5) — количество дней.

Во второй строке заданы n целых чисел a_i (-10^9 <= a_i <= 10^9) — продажи по дням.

В третьей строке задано число q (1 <= q <= 2 * 10^5) — количество запросов.

В следующих q строках заданы пары чисел l и r (1 <= l <= r <= n) — границы периода.

Выходные данные

Для каждого запроса выведите на отдельной строке одно число — сумму продаж на отрезке [l, r].

Ответы могут не помещаться в 32-битный целочисленный тип.

Ограничения

• 1 <= n <= 2 * 10^5
• -10^9 <= a_i <= 10^9
• 1 <= q <= 2 * 10^5
• 1 <= l <= r <= n

Примеры

Пример 1

Входные данные

1
1000000000
1
1 1

Выходные данные

1000000000

Пример 2

Входные данные

5
1000000000 -1000000000 1000000000 -1000000000 1000000000
6
1 1
5 5
1 5
2 4
3 3
1 3

Выходные данные

1000000000
1000000000
1000000000
-1000000000
1000000000
1000000000