题目描述

现在面条老师持有$n$个宝可梦。每个宝可梦具有一个能力值。面条老师想要选出来一系列宝可梦，使得这些宝可梦构成$[l, r]$的一个排列。

面条老师具有无限数量的进化药水，可以帮助宝可梦提升能力值。具体来说，对于每个宝可梦，面条老师可以使用进化药水提升1点能力值。只不过药水的作用是有限的，对于每个宝可梦，至多可以通过进化药水提升$k$次能力值。

每次询问一个区间$[l, r]$，你需要回答是否有方案使得在初始的宝可梦里选出若干宝可梦，对他们使用进化药水之后可以得到一个$[l, r]$的排列。

输入格式

第一行两个整数$n, k, q$，表示一共有$n$个宝可梦，每个宝可梦能够使用的进化药水次数$k$，共会有$q$次询问。

接下来一行$n$个正整数，依次表示每个宝可梦的能力值。

接下来$q$行，每行两个整数$l, r$（保证$l \le r$），表示本次询问的区间$[l, r]$

输出格式

对于每个询问，打印YES或NO表示是否存在对应方案。

5 2 4
2 2 2 2 2
2 3
1 2
2 5
3 4

YES
NO
NO
YES

样例解释

对于第一个询问，选择一组[2, 2]，对其中一个宝可梦用一次进化药水，可以得到[2, 3]。

对于第二个询问，由于不存在能变成能力值1的宝可梦，所以不存在方案。

对于第三个询问，不存在能变成能力值5的宝可梦，所以不存在方案。

对于第四组询问，选出两个宝可梦，一个变成3，一个变成4即可。

数据规模与约定

对于20%的数据，$1 \le n, q \le 10, k \le 10, 1 \le l \le r \le n + k$

对于50%的数据，$1 \le n, q \le 100, k \le 50, 1 \le l \le r \le n + k$

对于100%的数据，$1 \le n, q \le 10^5, k \le 50, 1 \le l \le r \le n + k$

对于所有数据保证初始给定的能力值$a_i$满足$1 \le a_i \le n$。

大样例

大样例下载