题目描述

某座城市最近在城市的主干道上安装了一套“道路监控定位系统”，用于追踪道路上车辆的分布情况。

城市的主干道可以看做一条从左向右的数轴，最左侧的起点可视为数轴 $0$ 的位置。在某时刻，系统记录了 $N$ 辆车辆在城市主干道上的位置坐标。为了进行统计分析，指挥中心提出了 $Q$ 个查询请求。每个请求给出一个坐标区间 $[S_i, T_i]$，希望统计在这个区间内共有多少辆车（含 $S_i$ 位置和 $T_i$ 位置）。

请你编写程序，帮助系统快速回答所有查询。

输入格式

第一行包含两个整数 $N$ 和 $Q$，分别表示记录的车辆数量和查询的数量。

第二行包含 $N$ 个互不相同的整数，表示每辆车在道路上的坐标位置。

接下来 $Q$ 行，每行包含两个整数 $S_i$ 和 $T_i$，表示一次查询，询问在区间 $[S_i, T_i]$ 内有多少辆车。

输出格式

输出共 $Q$ 行。对于每个查询，输出一个整数，表示该区间内的车辆数量。

样例

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

2
2
3

10 5
4 9 11 33 36 42 47 15 18 25
0 10
10 20
20 35
0 50
40 45

2
3
2
10
1

样例解释

样例 1
车辆位置：$2, 5, 8, 13, 17$。

• 询问 1：区间 $[0,5]$ → 车辆在 $2$、$5$，共 $2$ 辆。
• 询问 2：区间 $[6,15]$ → 车辆在 $8$、$13$，共 $2$ 辆。
• 询问 3：区间 $[8,20]$ → 车辆在 $8$、$13$、$17$，共 $3$ 辆。

数据范围与提示

• 对于 $10\%$ 的数据：$1 \le N, Q \le 100$，车辆位置均在 $[0, 100]$ 范围内，且互不相同，$0 \le S_i \le T_i \le 100$。
• 对于 $20\%$ 的数据：$1 \le N, Q \le 1000$，车辆位置均在 $[0, 10^7]$ 范围内，且互不相同，$0 \le S_i \le T_i \le 10^7$。
• 对于 $100\%$ 的数据：$1 \le N, Q \le 10^5$，车辆位置均在 $[0, 10^9]$ 范围内，且互不相同，$0 \le S_i \le T_i \le 10^9$。