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

Условие

Дан массив целых чисел a₁, a₂, ..., a_N и дано M команд типа "найти сумму чисел a_i для i от l до r".

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000000

1 ≤ M ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

1 ≤ l_j ≤ r_j ≤ N

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

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

6 14 12