C++ / 观测站的温度记录 算法挑战

观测站的温度记录

观测站保存了 n 天的温度变化值。接下来有 q 次查询，每次给出起止日期 l 和 r，请输出这段日期（包含两端）的变化值总和。变化值可以是负数。

输入格式

第一行两个整数 n、q。第二行 n 个整数。接下来 q 行，每行两个整数 l、r。

输出格式

每次查询输出一行，表示对应区间的总和。

数据范围

1 ≤ n, q ≤ 100000；−10⁹ ≤ aᵢ ≤ 10⁹；1 ≤ l ≤ r ≤ n。

样例输入

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

样例输出

4
1
1

样例说明

第一个查询的结果是 2 + (−3) + 5 = 4。