题目描述

某座城市最近在城市的主干道上，安装了一套“道路监控定位系统”，用于追踪道路上车辆的分布情况。 城市的主干道可以看做一条从左向右的数轴，最左侧的起点可以视为数轴 0 的位置。 在某时刻，系统记录了 N 辆车辆在城市主干道上的位置坐标。为了进行统计分析，指挥中心提出了 Q 个查询请求。每个请求给出一个坐标区间 [S_i, T_i] ，希望统计在这个区间内共有多少辆车（含 S_i 位置和 T_i 位置）。 请你编写程序，帮助系统快速回答所有查询。

输入格式

第一行包含两个整数 N 和 Q ，分别表示记录的车辆数量和查询的数量。 第二行包含 N 个互不相同的整数，表示每辆车在道路上的坐标位置。 接下来 Q 行，每行包含两个整数 S_i 和 T_i ，表示一次查询，询问在区间 [S_i, T_i] 内有多少辆车。

输出格式

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

样例输入 1

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

样例输出 1

2
2
3

样例输入 2

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

样例输出 2

2
3
2
10
1

样例输入 3

20 10
3 7 10 14 18 22 27 31 35 40 46 53 60 67 72 80 85 90 95 99
0 10
10 20
20 50
0 100
50 100
30 70
15 25
60 75
80 100
0 5

样例输出 3

3
3
6
20
9
7
2
3
5
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 ≤ N, Q ≤ 100 ，每辆车在主干道的位置均在 [0, 100] 的范围内，且互不相同，0 ≤ S_i ≤ T_i ≤ 100。
• 对于 20% 的数据，满足 1 ≤ N, Q ≤ 1000 ，每辆车在主干道的位置均在 [0, 1e7] 的范围内，且互不相同，0 ≤ S_i ≤ T_i ≤ 1e7。
• 对于 100% 的数据，满足 1 ≤ N, Q ≤ 1e5 ，每辆车在主干道的位置均在 [0, 1e9] 的范围内，且互不相同，0 ≤ S_i ≤ T_i ≤ 1e9。