Знакопеременная сумма
Автор задачи: Сергей Штейнер
Задачу добавил: shtserg
Успешно сдано решений: 12
Дано n натуральных чисел ai, 1 <= n <= 105, -109 <= ai <= 109, 1 <= i <= n.
Кроме того, есть m запросов, 1 <= m <= 105. Каждый запрос представляет собой пару чисел i1, i2, 1 <= i1 <= i2 <=n.
В ответ на каждый запрос необходимо вывести знакопеременную сумму ai1 - ai1+1 + ... + (-1) i2-i1 ai2.
Во входном файле в первой строчке записано число n, в следующих n строках - все числа ai.
Далее записано число m. В следующих m строках записано по паре чисел, описывающих запросы.
Выходной файл должен содержать m чисел, записанных в разных строках, i-е число - ответ на i-й запрос.
Пример
input.txt
10
1
2
3
4
5
6
7
8
9
10
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
output.txt
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-5
Замечание.
Решения, верно работающие для m+n <= 2000, будут оцениваться не менее чем в 36 баллов.
Решения, верно работающие для n <= 2000, будут оцениваться не менее чем в 45 баллов.