Сумма значений в промежутке

Дан список из $n$ чисел по неубыванию и $q$ запросов.

Для каждого запроса — пары $L$ и $R$ — выведите сумму всех элементов со значением от $L$ до $R$ включительно.

В первой строке число $n$ от $1$ до $2 \cdot 10^5$. Во второй — $n$ чисел от $-10^9$ до $10^9$ по неубыванию. В третьей — число $q$ от $1$ до $10^5$. В четвёртой — $2q$ чисел: пары $L$ и $R$ подряд, причём $L \le R$.

$q$ чисел через пробел.

Границы промежутка ищутся поиском, а сумма между ними берётся из накопленных сумм прошлого занятия.