题目描述

给定一个包含 $n$ 个整数的非递减序列。现有 $q$ 次询问，每次给出两个整数 $L,R$，请计算序列中有多少个数位于闭区间 $[L,R]$ 内。

输入格式

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

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，保证序列非递减。

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

输出格式

对每次询问输出一行，表示满足 $L\le a_i\le R$ 的元素个数。

样例

7 4
-3 1 1 4 7 7 9
-10 0
1 7
8 100
7 7

1
5
1
2

数据规模与约定

• $1\le n,q\le2\times10^5$；
• $-10^9\le a_i,L,R\le10^9$；
• $L\le R$，且数组非递减。