• 文件输入：battle.in
• 文件输出：battle.out
• 时间限制：4s
• 空间限制：512MB

题目描述

小明正在玩一款电脑游戏。他开始游戏时等级为 $1$。他即将按从 $1$ 到 $n$ 的顺序与 $n$ 个怪物战斗。第 $i$ 个怪物的等级是 $a_i$。

对于给定顺序中的每个怪物，小明的遭遇如下：

• 如果小明的等级严格高于怪物的等级，怪物就会逃跑；
• 否则，小明与怪物战斗。

在每第 $k$ 次与怪物战斗后（逃跑的怪物不计入），小明的等级增加 $1$。因此，在他战斗了 $k$ 个怪物后等级变为 $2$，$2k$ 个怪物后变为 $3$，$3k$ 个怪物后变为 $4$，依此类推。

你需要处理 $q$ 个如下形式的查询：

• $i~x$：如果参数 $k$ 等于 $x$，小明会与第 $i$ 个怪物战斗吗（还是这个怪物会逃跑）？

输入格式

第一行包含两个整数 $n$ 和 $q$ —— 怪物数量和查询数量。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ —— 怪物的等级。

接下来 $q$ 行中的第 $j$ 行，包含两个整数 $i$ 和 $x$ —— 第 $j$ 个查询中怪物的索引以及升级所需的战斗次数。

输出格式

对于每个查询，如果 小明在该查询中会与第 $i$ 个怪物战斗，则输出 YES；如果第 $i$ 个怪物逃跑，则输出 NO。

样例

4 16
2 1 2 1
1 1
2 1
3 1
4 1
1 2
2 2
3 2
4 2
1 3
2 3
3 3
4 3
1 4
2 4
3 4
4 4

YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES

7 15
1 1 2 1 1 1 1
5 3
2 2
2 2
1 6
5 1
5 5
7 7
3 5
7 4
4 3
2 5
1 2
5 6
4 1
6 1

NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO

说明/提示

数据规模与约定

对于所有的数据，$1 \le n, q \le 2 \cdot 10^5$，$1 \le a_i \le 2 \cdot 10^5$，$1 \le i, x \le n$。

• 特殊性质A：$a_i$ 各不相同；
• 特殊性质B：对于任意 $1 \le i \le n$，均有 $a_i \le 10$

测试样例

一共 $5$ 组测试样例。

$battle\texttt{i}.in$ 和 $battle\texttt{i}.ans$ 对应子任务 $i$。

点击下载 测试样例