题目描述

农夫John在一条穿过他的农场的路上（直线）放了 $N$ 个干草垛（$1 \leq N \leq 100,000$），每个干草垛都在不同的点上。为了让每个干草垛之间都隔着一定的距离，请你回答农夫John的 $Q$ 个问题（$1 \leq Q \leq 100,000$），每个问题都会给出一个范围，询问在这个范围内有多少个干草垛。

（其实就是有一条数轴上有 $N$ 个不重复的点，再问 $Q$ 个问题，每个问题是给出一个范围，问此范围内有多少个点？）

输入格式

第一行包括 $N$ 和 $Q$。

第二行有 $N$ 个数字，每个数字的范围在 $0 \leq x \leq 1,000,000,000$，表示此位置有一个干草垛。

接下来的 $Q$ 行，每行包括两个数字 $A$ 和 $B$ （$0 \leq A \leq B \leq 1,000,000,000$）表示每个询问的范围。

输出格式

总共 $Q$ 行，每行输出此范围内的干草垛数量。

输入样例

4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10

输出样例

2
2
3
4
1
0