Canadian Computing Olympiad: 2022 Day 1, Problem 1

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,\dots ,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],\dots ,h[K]$ such that $h[A_x]>h[A_{x+1}]<h[A_{x+2}]>h[A_{x+3}]<\dots 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$.

Input Specification

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,\dots ,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)$.

Marks Awarded	Bounds on $N$	Bounds on $K$	Bounds on $Q$
$4$ marks	$2\le N\le 3000$	$K=2$	$1\le Q\le {10}^6$
$6$ marks	$2\le N\le 500$	$2\le K\le min(N,5)$	$1\le Q\le {10}^6$
$7$ marks	$2\le N\le 3000$	$2\le K\le N$	$1\le Q\le 2000$
$8$ marks	$2\le N\le 3000$	$2\le K\le N$	$1\le Q\le {10}^6$

Output Specification

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.

Sample Input

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

Output for Sample Input

NO
YES
NO

Explanation of Output for Sample Input

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]$.