题目描述

译自 CCO 2022 Day1 T1「Alternating Heights」。

Troy 计划给 CCO 的学生拍一张合影，他向你寻求帮助。

有 $K$ 个学生，编号从 $1$ 到 $K$。Troy 忘记了学生的身高，但他记得没有两个学生的身高相同。

Troy 有一个序列 $A_{1}, A_{2}, \ldots, A_{N}$，表示合影中从左到右的学生顺序。一个学生可能在 $A$ 中出现多次。你不知道这张合影会怎么拍，但你不愿意认为 Troy 犯了错误。

Troy 会给你 $Q$ 个形式为 $x\ y$ 的询问，每个询问为「给定学生序列 $A_{x}, A_{x+1}, \ldots, A_{y}$，他们的身高能否形成一个交替序列？」更具体地说，我们用 $h_i$ 表示第 $i$ 个学生的身高。如果存在一种身高分配 $h_1, h_2, \ldots, h_K$，使得 $h_{A_{x}} > h_{A_{x+1}} < h_{A_{x+2}} > h_{A_{x+3}} < \ldots h_{A_{y}}$，回答 YES；否则回答 NO。

注意，每个查询都是独立的：也就是说，询问 $i$ 的身高分配与询问 $j$ 的身高分配无关 $(i \neq j)$。

输入格式

第一行包含三个用空格分隔的整数 $N, K, Q$。

第二行包含 $N$ 个整数，表示 $A_{1}, A_{2}, \ldots, A_{N}$。

接下来的 $Q$ 行，每行包含两个用空格分隔的整数 $x$ 和 $y$ $(1 \leq x < y \leq N)$，表示一组查询。

输出格式

输出 $Q$ 行。第 $i$ 行，输出 YES 或者 NO，表示 Troy 的第 $i$ 个查询的答案。

样例

输入

6 3 3
1 1 2 3 1 2
1 2
2 5
2 6

输出

NO
YES
NO

样例解释

• 对于第一个询问，序列为 $A_1, A_2 = [1, 1]$，不可能有 $h_1 > h_1$（身高互不相同），所以答案是 NO。
• 对于第二个询问，序列为 $A_2, A_3, A_4, A_5 = [1, 2, 3, 1]$，需要满足 $h_1 > h_2 < h_3 > h_1$。一种合法方案是 $h_1=160\ \text{cm}, h_2=140\ \text{cm}, h_3=180\ \text{cm}$（验证：$160>140<180>160$），所以答案是 YES。
• 对于第三个询问，序列为 $A_2, A_3, A_4, A_5, A_6 = [1, 2, 3, 1, 2]$，需要满足 $h_1 > h_2 < h_3 > h_1 < h_2$。但前两个条件要求 $h_1 > h_2$，最后一个条件要求 $h_1 < h_2$，矛盾，所以答案是 NO。

数据范围与提示

对于所有的数据，有 $2 \leq N \leq 3000$，$2 \leq K \leq N$，$1 \leq A_{i} \leq K$，$1 \leq Q \leq 10^6$。

详细子任务附加限制及分值如下表所示：