Дневник дежурного: сумма за период

В школе дежурный по параллели каждый день записывает, на сколько «баллов порядка» изменилась обстановка: положительное число — стало лучше, отрицательное — стало хуже.

Завуч задаёт много вопросов вида: «каков общий итог за дни с L по R включительно?»

Нужно быстро отвечать на все такие вопросы.

Формат ввода

В первой строке дано целое число n — число дней. Во второй строке даны n целых чисел a1, a2, ..., an — изменения баллов порядка по дням. В третьей строке дано целое число q — число вопросов завуча. Далее в q строках даны пары целых чисел L R (1 ≤ L ≤ R ≤ n) — границы периода.

Формат вывода

Выведите q строк. В i-й строке выведите общий итог (сумму) за дни с L по R включительно для i-го вопроса.

Ограничения

• 1 ≤ n ≤ 200000
• 1 ≤ q ≤ 200000
• -10^9 ≤ ai ≤ 10^9
• Суммы могут не помещаться в 32-битный тип (как на олимпиадах), используйте 64-битную арифметику.

Пример

Ввод:

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

Вывод:

5
-2
1