题目描述

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

输入格式

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

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

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

输出格式

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