题目描述

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

城市的主干道可以看做一条从左向右的数轴，最左侧的起点可以视为数轴 $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

输出

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
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$。