Troy 计划为 CCO 的学生拍摄一张合影，并向你寻求帮助。
共有 $K$ 名学生，编号为 $1$ 到 $K$。Troy 忘记了学生们的身高，但他记得没有两名学生的身高相同。
Troy 准备了一个序列 $A_1, A_2, \dots, A_N$，代表合影中从左到右的学生排列顺序。同一个学生可能会在 $A$ 中出现多次。你不确定这张合影是如何拍摄的，但你不愿假设 Troy 犯了错误。
Troy 将向你提出 $Q$ 个询问，每个询问包含 $x$ 和 $y$，这是一种简洁的提问方式，意为：“给定学生序列 $A_x, A_{x+1}, \dots, A_y$，他们的身高能否构成一个交替序列？”更准确地说，我们将第 $i$ 名学生的身高记为 $h[i]$。如果存在一种身高分配方案 $h[1], h[2], \dots, h[K]$，使得 $h[A_x] > h[A_{x+1}] < h[A_{x+2}] > h[A_{x+3}] < \dots h[A_y]$ 成立，则回答 YES；否则回答 NO。
注意，这 $Q$ 个询问是相互独立的：也就是说，对于询问 $i$ 的身高分配与对于询问 $j$ 的身高分配无关（只要 $i \neq j$）。
输入格式
第一行包含三个空格分隔的整数 $N, K$ 和 $Q$。
第二行包含数组 $A_1, A_2, \dots, A_N$ ($1 \le A_i \le K$)。
接下来的 $Q$ 行，每行包含一个询问，由两个空格分隔的整数 $x$ 和 $y$ ($1 \le x < y \le N$) 组成。
子任务
| 分值 | $N$ 的范围 | $K$ 的范围 | $Q$ 的范围 |
|---|---|---|---|
| 4 分 | $2 \le N \le 3000$ | $K = 2$ | $1 \le Q \le 10^6$ |
| 6 分 | $2 \le N \le 500$ | $2 \le K \le \min(N, 5)$ | $1 \le Q \le 10^6$ |
| 7 分 | $2 \le N \le 3000$ | $2 \le K \le N$ | $1 \le Q \le 2000$ |
| 8 分 | $2 \le N \le 3000$ | $2 \le K \le N$ | $1 \le Q \le 10^6$ |
输出格式
输出 $Q$ 行。第 $i$ 行输出对 Troy 第 $i$ 个询问的回答。注意，回答应为 YES 或 NO。
样例
输入 1
6 3 3 1 1 2 3 1 2 1 2 2 5 2 6
输出 1
NO YES NO
说明
对于第一个询问，我们永远无法满足 $h[1] > h[1]$，因此答案为 NO。
对于第二个询问，满足 $h[1] > h[2] < h[3] > h[1]$ 的一种方案是 $h[1] = 160\text{cm}, h[2] = 140\text{cm}, h[3] = 180\text{cm}$。另一种方案可以是 $h[1] = 1.55\text{m}, h[2] = 1.473\text{m}, h[3] = 1.81\text{m}$。
对于第三个询问，我们无法同时满足 $h[1] > h[2]$ 和 $h[1] < h[2]$。