Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Рубка деревьев

Чубатый учит Григория Мелехова выполнять баклановский удар шашкой. В качестве целей они используют n деревьев, стоящих в ряд и пронумерованных от 1 до n. Чубатый оценил прочность всех деревьев натуральными числами и записал их. За каждое дерево, которое Мелехов смог разрубить, он получает количество очков равное числу, записанному на дереве, а если не смог - то теряет столько же.
Чубатый просит Григория выполнить удары на деревьях с l по r, в порядке возрастания их номеров. Мелехов недавно ушиб плечо, потому он может успешно срубить дерево через раз, т. е. если он срубил дерево с номером i, то он не сможет срубить дерево с номером i + 1, но сможет срубить дерево с номером i + 2 и т. д.
Мелехов m раз попросил Григория выполнить удары, но он забыл, какие деревья Мелехов смог срубить. Помогите ему определить, сколько очков набрал Григорий за каждую попытку.
 
Входные данные
В первое строке содержатся 2 числа n и m (1 <= n, m <= 100000)
Во второй строке содержатся n чисел - прочность всех деревьев, где на позиции i написана прочность дерева i.
В следующих m строках содержатся пары чисел l и r (1 <= l <= r <= n), означающие какой отрезок деревьев попросил срубить Чубатый.
 
Выходные данные
На каждый запрос выведите сколько очков в эту попытку заработал Григорий.

Ввод Вывод
6 6
1 2 3 4 5 6
1 6
1 5
2 6
2 5
2 4
2 2
57
-92
57
-130

(с) Григорьев Е., 2018


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: