ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1330. Интервалы

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
— Суеверия… Предрассудки… — рассеянно проговорил незнакомец. — Леность ума и зависть, зависть, поросшая волосами зависть… — Он прервал самого себя. — Простите, Александр Иванович, но я бы осмелился все-таки просить вашего разрешения убрать этот ковш. К сожалению, железо практически не прозрачно для гиперполя, а возрастание напряженности гиперполя в малом объеме…
После инцидента с “идеальным потребителем” Выбегалло в НИИ ЧАВО спешно вводят автоматизированную систему безопасности. Она должна гарантировать, что в любом объеме общая интенсивность гиперполя не превышает критическую величину. На Сашу Привалова и его Алдан возложена важная задача по автоматической обработке показаний датчиков, расставленных по всему НИИ.
Все датчики занумерованы от 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 года)