题目描述

数轴上有 $N$ 个互不相同的车辆位置。现有 $Q$ 次询问，每次给出闭区间 $[S_i,T_i]$，请求出该区间内车辆的数量。

输入格式

第一行包含两个整数 $N,Q$。 第二行包含 $N$ 个互不相同的整数，表示车辆位置。 接下来 $Q$ 行每行包含两个整数 $S_i,T_i$。

输出格式

输出 $Q$ 行，每行一个整数，表示对应区间内的车辆数量。

样例

5 3
2 13 17 5 8
0 5
6 15
8 20

2
2
3

数据范围与提示

• $1 \le N,Q \le 10^5$
• 车辆位置及询问端点均在 $[0,10^9]$ 内
• $S_i \le T_i$。