eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сумма на отрезке

Сумма на отрезке

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Задан набор чисел a_1, ..., a_n. Для заданных индексов l и r найдите

S_{l,r} = a_l + a_{l+1} + ... + a_r

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

В первой строке записано количество чисел n~(1 \le n \le 10^6). Во второй строке записаны числа a_i~(1 \le a_i \le 1000). В третьей строке записано количество запросов m~(1 \le m \le 10^6). Далее на отдельных строках записаны сами запросы l_i и r_i~(1 \le l_i \le r_i \le n).

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

Выведите в отдельных строках m чисел S[l_i ... r_i].

Пример

Входные данные #1
5
1 2 3 4 5
5
1 5
2 3
3 4
2 5
1 4
Выходные данные #1
15
5
7
14
10
Автор В.Гольдштейн
Источник Зимние сборы в Харькове 2010 День 2