Дан неизменяемый массив длины n и q запросов типа “вычислить сумму подотрезка массива с l по r”. Выведите ответ на каждый запрос.
Входные данные
В первой строке дано число n – размер массива (\(1 <= n <= 10^5\)). Во второй строке дано n чисел – элементы массива. Числа по модулю не превосходят \(10^9\). В третьей строке дано число q – кол-во запросов (\(1 <= q <= 10^5\)). Далее дано q строк, в каждой из которых дано 2 числа: l и r (\(1 <= l <= r <= n\)).
Выходные данные
Выведите ответы на все запросы, каждый в отдельной строке.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
1 2 3 4 5
3
1 2
3 3
2 5
|
3
3
14 |