Basic Binary Search

Basic Binary Search

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

I/O格式

输入

第一行是两个正整数N,QN, Q
第二行是NN个正整数a1,a2aNa_1, a_2 \cdots a_N
之后QQ行,每行两个正整数C,RC, R,表示该次询问的参数。

输出

输出QQ行,每行一个非负整数表示该次询问的结果。输出的顺序与输入时询问的顺序一致。

样例

输入

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

输出

2
1
0

数据规模及约定

N,Q105;xai,C105N, Q \le 10^5; \phantom{x} a_i, C \le 10^5
50%的数据:R20R \le 20
100%的数据:R105R \le 10^5

限制

1s, 64MB

2019.1.25 TYWZ高一集训 Day2

未参加
状态
已结束
规则
OI
题目
2
开始于
2019-01-25 16:45
结束于
2019-01-25 17:03
持续时间
0.3 小时
主持人
参赛人数
21