Task
Time limit:
1000 ms,
Memory limit:
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