题目描述

给定一个正整数序列\(\{ a_i \}, i = 1, 2 \cdots N\)，以及\(Q\)次询问，每次询问给定两个参数\(C, R\)，求序列\(\{ a_i \}\)的\(N\)个数中，有多少个数位于闭区间\([C - R, C + R]\)内。

I/O格式

输入

第一行是两个正整数\(N, Q\)；
第二行是\(N\)个正整数\(a_1, a_2 \cdots a_N\)；
之后\(Q\)行，每行两个正整数\(C, R\)，表示该次询问的参数。

输出

输出\(Q\)行，每行一个非负整数表示该次询问的结果。输出的顺序与输入时询问的顺序一致。

样例

输入

6 3
50 40 60 80 20 30
15 15
64 12
45 4

输出

2
1
0

数据规模及约定

\(N, Q \le 10^5; \phantom{x} a_i, C \le 10^5\)
50%的数据：\(R \le 20\)
100%的数据：\(R \le 10^5\)

限制

1s, 64MB