Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида l, r (\(1 <= l <= r <= n\)).
На каждый запрос нужно вывести сумму чисел на отрезке от l до r включительно. Элементы нумеруются с 1 до n.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1 2 3 4
2
1 4
1 1
|
10
1 |
| 2 |
5
5 5 5 5 5
1
5 5
|
5 |