Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Рубка деревьев

Префиксные суммы(минимумы, ...)

Чубатый учит Григория Мелехова выполнять баклановский удар шашкой. В качестве целей они используют 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