题目描述

农民约翰刚刚整理了他的$\red{N}$个草包$\red{（1≤}$$\red{N≤}$$\red{100000）}$沿着穿过农场的一维道路的各个点。为了确保它们的间距适当，请帮助他回答$\red{Q}$问题$\red{（1≤}$$\red{Q≤}$$\red{100000）}$，每个人询问道路上特定间隔内的草包数量。

输入格式

第一行包含$\red{N}$和$\red{Q}$。

下一行包含$\red{N}$个不同的整数，每个整数的范围为$\red{0…}$$\red{100000000，}$表示每个位置都有一个干草捆。

接下来的每条$\red{Q}$线包含两个整数$\red{A}$和$\red{B（}$$\red{0≤}$$\red{A≤}$$\red{B≤}$$\red{100000000）}$查询$\red{A}$和$\red{B}$之间的草包数量。

输出格式

你应该写$\red{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