题目描述

给定一个长度为 $n$ 的整数数组 $a$，有 $q$ 次询问。每次询问给出区间 $[L,R]$，请回答这个区间内有多少个偶数。

输入格式

第一行输入两个整数 $n,q$，分别表示数组长度和询问次数。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行输入两个整数 $L,R$，表示一次询问的区间。

输出格式

输出 $q$ 行，第 $i$ 行输出第 $i$ 次询问的答案。

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

2
1
3

数据范围与提示

• $1 \le n \le 10^6$
• $1 \le q \le 10^6$
• $1 \le L \le R \le n$
• $1 \le a_i \le 10$

可以预处理前缀和：令 $s_i$ 表示前 $i$ 个数中偶数的个数，则区间 $[L,R]$ 的答案为 $s_R-s_{L-1}$。