PRE501 操场温度记录

难度梯度：T2｜训练重点：一维前缀和

题目描述

连续 N 天记录每天的温度变化量 a_i（可能为负数）。有 Q 次询问，每次给出闭区间 [l,r]，输出这几天温度变化量之和。每次询问彼此独立。

这里求的是每日变化量之和，而不是某一天的绝对温度；问答区间左右端点都包含在内。

输入格式

第一行 N Q；第二行 N 个整数 a_i；接下来 Q 行，每行 l r。

输出格式

每次询问输出一行整数。

样例输入

5 3
2 -1 4 -3 5
1 3
2 4
4 5

样例输出

5
0
2

样例说明

例如 [2,4] 的和为 -1+4-3=0。

数据范围

1≤N,Q≤2×10^5；-10^9≤a_i≤10^9；1≤l≤r≤N。

子任务

30 分：N,Q≤1000；70 分：无附加限制。