Sequence Game

The operation looks like it might care about adjacency, order, or some galaxy-brain interval DP. It does not. This is an 800, so the trick is noticing the whole game collapses to one range check.

Let

$$L = \min(a_1,a_2,\ldots,a_n), \qquad R = \max(a_1,a_2,\ldots,a_n).$$

The answer is:

$$\texttt{YES} \iff L \le x \le R.$$

Why outside the range is impossible

When you merge two adjacent values $p$ and $q$, the replacement value $y$ must satisfy

$$\min(p,q) \le y \le \max(p,q).$$

So this merge cannot create a value smaller than both inputs, and it cannot create a value larger than both inputs.

That means no operation can ever create a number outside the initial global range $[L,R]$. The minimum can only increase or stay the same, and the maximum can only decrease or stay the same. So if $x<L$ or $x>R$, the final value being $x$ is impossible. Done.

Why every value inside the range is possible

Now suppose

$$L \le x \le R.$$

Then there exists at least one original element $\le x$ and at least one original element $\ge x$. Maybe one element is already exactly $x$, which is even easier.

Here is the useful way to think about merging:

• A value $\le x$ merged with another value $\le x$ can be replaced by some value still $\le x$.
• A value $\ge x$ merged with another value $\ge x$ can be replaced by some value still $\ge x$.
• A value $\le x$ merged with a value $\ge x$ can be replaced by exactly $x$.

So values have two “sides” relative to $x$: low side and high side. Merging two values on the same side can keep you on that side. Merging across the two sides lets you pick $x$ exactly.

Since the sequence is finite, keep merging adjacent elements while preserving the fact that there is still enough information to eventually have one low-side value and one high-side value. At the end, you can reduce the entire sequence to two values: one $\le x$ and one $\ge x$. Those two are adjacent because only two values remain. Then merge them into $x$.

No need to construct the actual operations in code. The existence argument is enough.

Edge case: $n=1$

If there is only one number, then $L=R=a_1$. The condition $L \le x \le R$ becomes $x=a_1$, which is exactly correct.

Algorithm

For each test case:

1. Read $n$, the array, and $x$.
2. Compute the minimum and maximum array values.
3. Print YES if $x$ lies between them, otherwise print NO.

Complexity

Each test case takes $O(n)$ time and $O(1)$ extra memory. Basically free, unless your computer is powered by a potato with commitment issues.