Farmer John 刚刚将他的 N 个干草捆 (1≤N≤100,000) 布置在穿过他农场的一维道路的各个点上。为了确保它们之间的间隔适当，请帮助他回答 Q 个问题（1≤Q≤100,000），每个问题都询问沿路特定间隔内的干草捆的数量。

输入格式（文件 haybales.in）：

第一行包含 N 和 Q。下一行包含 N 个不同的整数，每个整数都在 0…1,000,000,000 范围内，表示每个位置都有干草。

接下来的 Q 行中的每一行都包含两个整数 A 和 B (0≤A≤B≤1,000,000,000)，用于查询 A 和 B 之间（含）之间的干草堆数量。

输出格式（文件 haybales.out）：

你应该写 Q 行输出。对于每个查询，输出其各自区间内的干草数量。

SAMPLE INPUT:

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

SAMPLE OUTPUT:

2
2
3
4
1
0