Заданий масив з \(N\) чисел.
Зробіть програму яка буде швидко відповідати на запити: порахувати суму елементів масиву від \(L\) до \(R\)

Формат вхідних даних

В першому рядку ціле число \(N\) (\(1 \le N \le 10^6\))
В другому рядку записані елементи масиву \(Ai\) (\(1 \le Ai \le 1000 \)) розділені пробілом
В третьому рядку записано число \(M\) - кількість запитів. (\(1 \le M \le 10^6\))
В кожному з наступних \(M\) рядків міститься по два цілих числа \(L,R\) (\(1 \le L \le R \le N\)) - самі запити.

Формат вихідних даних

Для кожного запиту, в окремому рядку виведіть відповідь - суму елементів масиву від \(L\) до \(R\).

Приклад вхідних даних

5
1 2 3 4 5
5
1 5
2 3
3 4
2 5
1 4

Приклад вихідних даних

15
5
7
14
10