题目描述

某同学连续进行了 $n$ 天训练。第 $i$ 天的记录 $a_i$ 只有两种取值：

• 1：当天完成打卡；
• 0：当天没有完成打卡。

现在有 $q$ 次询问，每次给出一个日期区间 $[l,r]$，请统计这个区间内完成打卡的天数。

输入格式

第一行输入两个整数 $n,q$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，每个数为 0 或 1。

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

输出格式

每个询问输出一行，表示区间 $[l,r]$ 内 1 的个数。

样例

6 4
1 0 1 1 0 1
1 6
2 5
3 4
5 5

4
2
2
0

数据规模与约定

$1\le n,q\le 2\times 10^5$，$1\le l\le r\le n$。