— Суеверия… Предрассудки… — рассеянно проговорил незнакомец. — Леность ума и зависть, зависть, поросшая волосами зависть… — Он прервал самого себя. — Простите, Александр Иванович, но я бы осмелился все-таки просить вашего разрешения убрать этот ковш. К сожалению, железо практически не прозрачно для гиперполя, а возрастание напряженности гиперполя в малом объеме…
После инцидента с “идеальным потребителем” Выбегалло в НИИ ЧАВО спешно вводят автоматизированную систему безопасности. Она должна гарантировать, что в любом объеме общая интенсивность гиперполя не превышает критическую величину. На Сашу Привалова и его Алдан возложена важная задача по автоматической обработке показаний датчиков, расставленных по всему НИИ.
Все датчики занумерованы от 1 до N (1 ≤ N ≤ 10000). Показание i-го датчика напряженности гиперполя – это целое число
(-10000 ≤ ki ≤ 10000). Алдану необходимо быстро отвечать на запросы вида: чему равна сумма напряженностей на датчиках с i-го по j-й (i ≤ j). Число запросов Q может быть очень велико (0 ≤ Q ≤ 100000).
Исходные данные
В первой строке входа находится число N. Далее в следующих N строках записаны ki. Далее следует число Q и Q пар чисел i, j.
Результат
должен содержать Q строк с суммами соответствующих показаний датчиков напряженности.
Пример
исходные данные | результат |
---|
5
1
2
3
-1
4
3
1 5
4 4
1 4 | 9
-1
5 |
Автор задачи: Ден Расковалов
Источник задачи: Десятый командный чемпионат школьников Свердловской области по программированию (16 октября 2004 года)