Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Знакопеременная сумма

Автор задачи: Сергей Штейнер

Задачу добавил: 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 баллов.

Сдать задачу

Задать вопрос жюри по этой задаче