题目描述

农夫约翰刚刚在他的农场上沿着一维道路放置了 N 个干草堆（$1\le N\le 100,000$）。为了确保它们适当地间隔开，请帮助他回答 Q 个查询（$1\le Q\le 100,000$），每个查询都询问道路上特定区间内的干草堆数量。

输入格式

第一行包含 N 和 Q。

接下来一行包含 N 个不同的整数，每个整数在 0…1,000,000,000 的范围内，表示在这些位置上有一个干草堆。

接下来的 Q 行中，每行包含两个整数 A 和 B（$0\le A\le B\le 1,000,000,000$），表示查询 A 和 B 之间（包括 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

1 1
0
0 0

1

1 1  
0  
0 0

1

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

2
2
3
4
1
0