Задан числовой массив $A$[$1..n$]. Необходимо выполнить $m$ операций вычисления суммы на отрезке [$l$, $r$].

Входные данные

Первая строка содержит содержит число $n$ – размерность массива. Во второй строке записаны $n$ чисел – элементы массива. Третья строка содержит число $m$ – количество запросов суммы. Следующие $m$ строк содержат пары чисел $l$ и $r$ ($l ≤ r ≤ n$), описывающие отрезки. Все числа во входных данных натуральные, не превосходящие $10^5$.

Выходные данные

Для каждого запроса выведите искомую сумму через пробел.

Подзадачи