#P101. 加减法

加减法

题目描述:

有一个长度为nn的数组aa,数组下标从11开始。

现在小A想要练习加减法,所以他决定奇数下标上的数字用加法,偶数位上的数字用减法。

并且他想要通过qq次训练,每次训练计算区间[l,r][l,r]的结果。

即求∑i=lr(−1)i−1⋅ai=(−1)l−1⋅al+(−1)l⋅al+1+⋯+(−1)r−1⋅ar\sum\limits_{i=l}^{r}(-1)^{i-1}\cdot a_i=(-1)^{l-1}\cdot a_l+(-1)^{l}\cdot a_{l+1}+\cdots + (-1)^{r-1}\cdot a_r。

输入格式:

第一行两个正整数n,qn,q,表示数组长度和询问次数。 第二行nn个正整数aia_i,表示数组中元素。 接下来qq行,每行两个正整数l,rl,r,表示询问区间。

输出格式:

输出qq行,每行一个整数表示答案。

样例:

10 3
8 2 3 1 2 9 7 4 8 2
1 3
2 6
9 10
9 
-7
6

数据范围:

对于50%50\%的数据满足1≤n,q≤1001\le n,q\le 100。 对于所有数据满足1≤n,q≤105,1≤ai≤100,1≤l≤r≤n1\le n,q\le 10^5,1\le a_i\le 100,1\le l\le r\le n。

提示

a1−a2+a3=9a_1-a_2+a_3=9

−a2+a3−a4+a5−a6=−7-a_2+a_3-a_4+a_5-a_6=-7

a9−a10=6a_9-a_{10}=6