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

После подготовки данных поступает q запросов. Каждый запрос задаётся парой чисел l, r и означает: нужно мгновенно определить суммарные продажи за дни с l по r включительно. Нумерация дней начинается с 1.

Для каждого запроса выведите сумму продаж на соответствующем отрезке.

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

В первой строке задано число n — количество дней.

Во второй строке записаны n целых чисел a_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 4 5
3
1 5
2 3
4 4

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

15
5
4

Пояснение

Суммы: 15; 2+3=5; 4.

Пример 2

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

1
592
2
1 1
1 1

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

592
592