Chef goes Left Right Left
Chef is at a Code Expo where many coders are present discussing, solving, sharing, and eavesdropping on solutions 😛
He recently learnt that a former HackerPlant employee, Reziba, who is now working at KodeKarma stole some questions for their KoolKontest. Chef wants to find Reziba, but the only data he has on him, and everyone else present, are their CodeXP ratings, which are distinct.
Chef decides to find Reziba through his rating by asking different people present at the expo. Everyone present are arranged in such a way that, assuming a person with rating X, every person with a rating higher than X are on the person’s right, while every person with a rating lower than X are on the person’s left.
Everyone present there knows Reziba’s rating, except Chef, who now asks people where he could find Reziba.
Chef initially asks an arbitrary person, who replies by giving information on whether Reziba is to the person’s left or the person’s right, depending on whether this person has a higher or lower rating than Reziba.
Chef proceeds in that direction for an arbitrary distance and stops and asks the next person encountered, and repeats this procedure.
However, Chef will never go beyond a person whose rating Chef has asked before. For example, if Chef was walking to the left and finds a person who already told him to walk to the right then he will not continue going to the person’s left.
Chef finally finds Reziba when he finally stops in front of Reziba.
During Chef’s search for Reziba, he wrote the sequence of ratings of the people Chef asked in the exact same order, including Reziba’s rating, which is the last integer in the sequence.
Towards the end, Chef feels he might’ve made a mistake while writing this sequence.
Given the sequence that Chef wrote and Reziba’s rating, find out whether this sequence is possible or has mistakes.
- First line contains number of test cases T.
- The first line of each test case contains the number of people Chef meets, N and Reziba’s rating R seperated by a space.
- Second line of each test case contains N number of space separated ratings from A1 to AN where AN is always equal to R.
- For each test case, output a singe line with either “YES” if the sequence is correct, or print “NO” if the sequence has mistakes, without quotes.
- 1 ≤ T ≤ 50
- 1 ≤ N ≤ 106
- 1 ≤ sum of N in all test-cases ≤ 1.5*106
- 1 ≤ Ai ≤ 109
- Integers in A are distinct
- AN = R
- Subtask #1: N ≤ 20
- Subtask #2: Original Constraints
Input: 2 5 200 600 300 100 350 200 5 890 5123 3300 783 1111 890 Output: NO YES
Example test cases are running. There is some error coming with actual test cases. Trying to resolve.