区间销售额统计

题目描述

某商店连续记录了 n 天 的销售额。

第 i 天的销售额为 a[i]。

现在商店需要统计多个时间段内的销售总额。

共有 q 次查询，每次查询给出两个整数：

l r

表示查询从第 l 天到第 r 天（包含两天）的销售额总和。

请你计算每一次查询的结果。

计算公式：

$a_l+a_{l+1}+...+a_r$

输入格式

第一行输入两个整数：

n q

表示：

• n：销售记录的天数
• q：查询次数

第二行输入 n 个整数：

a1 a2 ... an

表示每天的销售额。

接下来 q 行，每行输入两个整数：

l r

表示一次查询的区间范围。

输出格式

对于每一次查询，输出一个整数：

表示第 l 天到第 r 天的销售总额。

每个答案占一行。

数据范围

1 ≤ n ≤ 100000
1 ≤ q ≤ 100000
0 ≤ a[i] ≤ 10000
1 ≤ l ≤ r ≤ n

保证所有计算结果均在 long long 类型范围内。

输入样例

5 3
10 20 30 40 50
1 3
2 5
4 4

输出样例

60
140
40