시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB56232242.308%

문제

Troy is planning to take a group photo of the students at CCO and has asked you for help.

There are $K$ students, numbered from $1$ to $K$. Troy has forgotten the students' heights but remembers that no two students have the same height.

Troy has prepared a sequence $A_1, A_2, \ldots, A_N$ representing the order of students in the group photo, from left to right. It is possible for a student to appear multiple times in $A$. You aren't sure how this group photo would be taken, but you're unwilling to assume that Troy made a mistake.

Troy will ask you $Q$ queries of the form x y, which is a compact way of asking "Given the sequence of students, $A_x, A_{x + 1}, \dots, A_y$, can their heights form an alternating sequence?" More precisely, we denote the height of the $i^\text{th}$ student as $h[i]$. If there exists an assignment of heights $h[1], h[2], \ldots, h[K]$ such that $h[A_x] > h[A_{x + 1}] < h[A_{x + 2}] > h[A_{x + 3}] < \ldots h[A_y]$, answer YES; otherwise, answer NO.

Note that each of the $Q$ queries will be independent: that is, the assignment of heights for query $i$ is independent of the assignment of heights for query $j$ so long as $i \ne j$.

입력

The first line of input will contain three space-separated integers $N$, $K$, and $Q$.

The second line of input will contain the array $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le K)$.

The next $Q$ lines will each contain a query of the form of two space-separated integers $x$ and $y$ $(1 \le x < y \le N)$.

출력

Output $Q$ lines. On the $i^\text{th}$ line, output the answer to Troy's $i^\text{th}$ query. Note that the answer is either YES or NO.

서브태스크

번호배점제한
14

$2 \le N \le 3\,000$, $K = 2$, $1 \le Q \le 10^6$

26

$2 \le N \le 500$, $2 \le K \le \min(N, 5)$, $1 \le Q \le 10^6$

37

$2 \le N \le 3\,000$, $2 \le K \le N$, $1 \le Q \le 2\,000$

48

$2 \le N \le 3\,000$, $2 \le K \le N$, $1 \le Q \le 10^6$

예제 입력 1

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

예제 출력 1

NO
YES
NO

힌트

For the first query, we will never have $h[1] > h[1]$, so the answer is no.

For the second query, one solution to $h[1] > h[2] < h[3] > h[1]$ is $h[1] = 160cm, h[2] = 140cm, h[3] = 180cm$. Another solution could be $h[1] = 1.55m, h[2] = 1.473m, h[3] = 1.81m$.

For the third query, we cannot have both $h[1] > h[2]$ and $h[1] < h[2]$.

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.