Задача F. Многократное суммирование

Автор:Г. Гренкин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Дан массив целых чисел a1, a2, ..., aN и дано M команд типа "найти сумму чисел ai для i от l до r".

Требуется написать программу, выполняющую данные команды.

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел ai.

Далее во входном файле содержится целое число M, за которым следуют M пар целых чисел lj rj.

Формат выходного файла

Выходной файл должен содержать M целых чисел — результаты выполнения команд.

Ограничения

1 ≤ N ≤ 1000000

1 ≤ M ≤ 1000000

 − 1000 ≤ ai ≤ 1000

1 ≤ lj ≤ rj ≤ N

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
1 2 3 4 5
3
1 3
2 5
3 5
6 14 12

0.101s 0.018s 15