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

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

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

Первая строка содержит целое число n — количество дней.

Во второй строке содержатся n целых чисел a_i, где a_i — объём продаж в i-й день.

В третьей строке содержится целое число q — количество запросов.

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

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

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

Ограничения

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

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

Примеры

Пример 1

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

5
1 -2 3 0 4
6
1 1
1 5
2 4
3 3
4 5
2 5

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

1
6
1
3
4
5

Пример 2

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

1
-1000000000
5
1 1
1 1
1 1
1 1
1 1

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

-1000000000
-1000000000
-1000000000
-1000000000
-1000000000