Chef goes Left Right Left
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Chef is at a Code Expo where many coders are present discussing, solving, sharing, and eavesdropping on solutions :P
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 case 1.The first person that Chef asked has a rating of 600, which is more than 200 so he tells Chef to go to his left. The second person Chef meets has a rating of 300, also tells Chef to go to the left. The third person that chef asked has a rating of 100 so he tells Chef to go to the right. Then Chef asked a person with rating 350, that means Chef went beyond the person with rating of 300, which should never happen, so Chef must have made a mistake while writing this sequence.
|Tags||abizerl123, cakewalk, nov17|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.