题目描述

Farmer John 刚刚将他的 $N$ 个干草捆（$1 \leq N \leq 100,000$）安排在他农场的一维道路上的各个位置。为了确保它们之间的间距合适，请帮助他回答 $Q$ 个查询（$1 \leq Q \leq 100,000$），每个查询询问在道路的特定区间内有多少个干草捆。

输入格式

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

第二行包含 $N$ 个不同的整数，每个整数的范围在 $0 \ldots 1,000,000,000$ 之间，表示每个位置上有一个干草捆。

接下来的 $Q$ 行每行包含两个整数 $A$ 和 $B$（$0 \leq A \leq B \leq 1,000,000,000$），表示一个查询，询问在 $A$ 到 $B$（包括 $A$ 和 $B$）的区间内有多少个干草捆。

输出格式

你需要输出 $Q$ 行。对于每个查询，输出其对应区间内的干草捆数量。

输入输出样例 #1

输入 #1

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

输出 #1

2
2
3
4
1
0