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 3\,000~	~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 3\,000~	~2 \le K \le N~	~1 \le Q \le 2\,000~
~8~ marks	~2 \le N \le 3\,000~	~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]~.