Problem Description

Troy plans to take a group photo of the CCO students, and he asks you for help.

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

Troy has a sequence $A_{1}, A_{2}, \ldots, A_{N}$, representing the order of students in the photo from left to right. A student may appear multiple times in $A$. You are not sure how this photo will be taken, but you do not want to believe that Troy made a mistake.

Troy will give you $Q$ queries of the form $x, y$. Each query asks: "Given the student sequence $A_{x}, A_{x+1}, \ldots, A_{y}$, can their heights form an alternating sequence?" More specifically, let $h_i$ be the height of student $i$. If there exists a height assignment $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}}$, output YES; otherwise output NO.

Note that each query is independent. That is, the height assignment for query $i$ is unrelated to the height assignment for query $j$ $(i \neq j)$.

Input Format

The first line contains three integers $N$, $K$, and $Q$, separated by spaces.

The second line contains $N$ integers representing $A_{1}, A_{2}, \ldots, A_{N}\left(1 \leq A_{i} \leq K\right)$.

The next $Q$ lines each contain two integers $x$ and $y$ separated by spaces $(1 \leq x<y \leq N)$, describing a query.

Output Format

Output $Q$ lines. On the $i$-th line, output YES or NO, indicating the answer to Troy's $i$-th query.

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

NO
YES
NO

Hint

Sample Explanation

For the first query, it is impossible to have $h_1>h_1$, so the answer is NO.

For the second query, one valid assignment for $h_1>h_2<h_3>h_1$ is $h_1=160 \mathrm{~cm}, h_2=140 \mathrm{~cm}, h_3=180 \mathrm{~cm}$. Another valid assignment is $h_1=1.55 \mathrm{~m}, h_2=1.473 \mathrm{~m}, h_3=1.81 \mathrm{~m}$.

For the third query, it is impossible to have both $h_1>h_2$ and $h_1<h_2$ at the same time.

Constraints

For all testdata, $2 \leq N \leq 3000$, $2 \leq K \leq N$, $1 \leq Q \leq 10^{6}$.

Translated by ChatGPT 5