[Solution] Nahaane Jaa CodeChef Solution

Problem

"Bapuji - Ae Jethiya Nahaane Jaa Nahaane Jaa".
Bapuji is furious with Jethiya because he did not bathe before eating. Jethiya does not want to bathe right now, but in order to do so, he must first establish his innocence to Bapuji.

Bapuji gives Jethiya a problem, and if Jethiya solves it, Bapuji will allow him to eat his food before taking a bath. Jethiya asks for your help to solve the problem.

You are given an array $A$ of size $N$ and an integer $K$. You can perform the following operation on the given array any number of times (possibly zero):

• Choose two integers $L$ and $R$ ($1 \leq L \leq R \leq N$)
• Then, for each $i$ such that $L \leq i \leq R$, set $A_i$ to $A_{\left\lfloor \frac{L+R}{2} \right\rfloor}$. Here, $\left\lfloor \ \right\rfloor$ denotes the floor function.
• That is, apply the following to the subarray $[L, R]$:
  • If this subarray has odd length, set all its elements to be equal to the middle element.
  • If it has even length, set all its elements to be equal to the left one among the two middle elements.

For example, if $A = [1, 3, 2, 3]$ then:

• If we choose $L = 1$ and $R = 4$, the array will change as follows: $[\underline{1, \textcolor{blue}{3}, 2, 3}] \to [3, 3, 3, 3]$
• If we choose $L = 2$ and $R = 4$, the array will change as follows: $[1, \underline{3, \textcolor{blue}{2}, 3}] \to [1, 2, 2, 2]$

Is it possible to make all the array elements equal to $K$ after performing some number of operations?

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of two lines of input.
  • The first line of each test case contains two space-separated integers $N$ and $K$ — the number of elements in the array and the value $K$ respectively.
  • The second line of each test case contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$ — the elements of the array.

Output Format

For each test case, output on a new line the answer: Yes if all the elements can be made equal to $K$, and No otherwise.

Each letter of the output may be printed in either uppercase or lowercase, i.e, Yes, YES, and yEs will all be treated as equivalent.

Explanation:

Test case $1$: There is no way to make all the elements of the array equal $10$.

Test case $2$: One way of performing operations is as follows:

• First, choose $L = 1$ and $R = 2$. This makes the array $[1, 1, 3]$.
• Then, choose $L = 1$ and $R = 3$. This makes the array $[1, 1, 1]$, and we are done.

Test case $3$: Choose $L = 1$ and $R = 5$. The middle element is $5$ so everything becomes $5$, as required.

Test case $4$: There is no way to make everything equal to $9$.