Given an array a of length n (\(1 <= n <= 2 \cdot 10^6\)< /span>, \(1 <= a_i <= 10^9\)). Also given m (\(1 <= m <= 500\)) queries like l, r (\(1 <= l <= r <= n\)).
For each query, print the sum of numbers between l and r inclusive. Elements are numbered starting with 1 to n.
Examples
| # |
Input |
Output |
| 1 |
4
1 2 3 4
2
1 4
1 1
|
10
1 |
| 2 |
5
5 5 5 5 5
1
5 5
|
5 |