题目描述

霸王龙运营了一个视频频道，并记录了连续 $n$ 天的粉丝净变化量。正数表示粉丝增加，负数表示粉丝减少。

现在需要回答 $q$ 次查询。每次给出两个日期 $l,r$，请计算从第 $l$ 天到第 $r$ 天（包含两端）的粉丝净变化总量。

输入格式

第一行包含两个整数 $n,q$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每天的粉丝净变化量。

接下来 $q$ 行，每行输入两个整数 $l,r$。

输出格式

对每次查询输出一行，表示指定日期区间内的粉丝净变化总量。

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

6
0
1

数据范围与提示

• $1\le n,q\le 2\times10^5$
• $-10^9\le a_i\le 10^9$
• $1\le l\le r\le n$