Farmer John は、農場を横切る一次元の道のさまざまな位置に $N$ 個の干し草の俵（$1 \leq N \leq 100,000$）を置いたところです。間隔が適切であることを確かめるため、$Q$ 個の質問（$1 \leq Q \leq 100,000$）に答えるのを手伝ってください。各質問では、道の指定された区間内にある干し草の俵の個数を尋ねます。

入力

最初の行には $N$ と $Q$ が与えられます。

次の行には $0 \ldots 1,000,000,000$ の範囲の相異なる $N$ 個の整数が与えられ、それぞれの位置に干し草の俵が 1 個あることを表します。

続く $Q$ 行にはそれぞれ 2 つの整数 $A$ と $B$（$0 \leq A \leq B \leq 1,000,000,000$）が与えられ、$A$ から $B$ まで（両端を含む）にある干し草の俵の個数を尋ねる質問を表します。

出力

$Q$ 行を出力してください。各質問に対して、対応する区間内の干し草の俵の個数を出力してください。

入出力例

入力 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

問題作成者：Nick Wu