Суммы на отрезках: префиксные суммы

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

Ввод: n (1 ≤ n ≤ 1500), n чисел по модулю до 10⁶, затем q (1 ≤ q ≤ 1500) и q строк l r (1 ≤ l ≤ r ≤ n).

Вывод: q строк с суммами.

Пример

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

15
5
4