CCO '22 P1 - Alternating Heights

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 1G

Author:
Problem type

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

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

Troy has prepared a sequence representing the order of students in the group photo, from left to right. It is possible for a student to appear multiple times in . 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 queries of the form x y, which is a compact way of asking "Given the sequence of students, , can their heights form an alternating sequence?" More precisely, we denote the height of the student as . If there exists an assignment of heights such that , answer YES; otherwise, answer NO.

Note that each of the queries will be independent: that is, the assignment of heights for query is independent of the assignment of heights for query so long as .

Input Specification

The first line of input will contain three space-separated integers , , and .

The second line of input will contain the array .

The next lines will each contain a query of the form of two space-separated integers and .

Marks AwardedBounds on Bounds on Bounds on
marks
marks
marks
marks

Output Specification

Output lines. On the line, output the answer to Troy's 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 , so the answer is no.

For the second query, one solution to is . Another solution could be .

For the third query, we cannot have both and .