Сумма на отрезке

Дан список из $n$ чисел и $q$ запросов. В каждом запросе указаны номера $l$ и $r$.

Для каждого запроса выведите сумму элементов с $l$-го по $r$-й включительно. Номера считаются с единицы.

В первой строке числа $n$ от $1$ до $2 \cdot 10^5$ и $q$ от $1$ до $10^5$. Во второй — $n$ целых чисел от $-10^9$ до $10^9$. В следующих $q$ строках — по два числа $l$ и $r$, причём $1 \le l \le r \le n$.

Числа через пробел — по одному ответу на запрос.

Считать сумму заново на каждый запрос — это до $n \cdot q$ действий. Посчитайте один раз накопленные суммы, и каждый ответ станет вычитанием.