Запросы суммы на отрезке

Условие

В первой строке дано n, во второй — n целых чисел. В третьей строке дано число запросов q. В каждой из следующих q строк даны l и r (1 ≤ l ≤ r ≤ n). Для каждого запроса выведите сумму элементов с a_l по a_r в отдельной строке.

Примеры

5
1 2 3 4 5
3
1 3
2 5
3 3

6
14
3

3
-1 -2 -3
2
1 3
2 2

-6
-2

Ограничения

• 1 ≤ n, q ≤ 10^5
• -10^9 ≤ a_i ≤ 10^9