题目描述

有一个整型数组 $a$，长度为 $n$，有 $q$ 次询问，每次询问需要查询数组从 $L$ 到 $R$ 这段范围内有多少个偶数。

输入格式

1. 第一行输入两个正整数 $n$ 和 $q$，分别表示数组的长度和询问次数；
2. 第二行输入 $n$ 个正整数，表示数组 $a$ 的具体内容；
3. 接下来 $q$ 行，每行输入两个正整数 $L$ 和 $R$，表示查询的范围。

数据范围

对于 100% 的数据：

• $1 \leq n \leq 10^6$
• $1 \leq q \leq 10^6$
• $1 \leq L \leq R \leq n$
• $1 \leq a[i] \leq 10$

输出格式

输出 $q$ 行，第 $i$ 行表示第 $i$ 次询问的结果（即区间 $[L, R]$ 内偶数的个数）。

输入输出样例

输入样例

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

输出样例

2
1
3

提示

• 第一次询问：从第1个数到第3个数，偶数有6、4，总计2个；
• 第二次询问：从第3个数到第3个数，偶数有4，总计1个；
• 第三次询问：从第1个数到第6个数，偶数有6、4、2，总计3个；