Brand New Tatar TV Show

Key observation

The game is monotone: after the last chosen value becomes $x$, nobody can ever choose a value smaller than $x$ again.

So forget array positions. Let $c_x$ be the frequency of value $x$.

Consider a state right after some value $x$ has just been chosen. Then:

• there are $c_x-1$ copies of $x$ left,
• all values $>x$ are untouched,
• all values $<x$ are irrelevant trash now.

Let $G_x$ be whether this state is winning for the player to move.

Arseniy wants to choose some value $x$ such that $G_x$ is winning for Egor.

What makes $G_x$ losing?

More generally, define $W(x,r)$ as the state where the last chosen value is $x$, there are $r$ copies of $x$ remaining, and all larger values are still available.

From $W(x,r)$, the current player can:

1. take another $x$, moving to $W(x,r-1)$, if $r>0$;
2. jump to some present value $y$ such that

$$x<y\le x+k,$$

which moves to $G_y$.

Now define

$$B_x = \text{“there exists } y\in(x,x+k] \text{ with } G_y \text{ losing”}.$$

If $B_x$ is true, then every state $W(x,r)$ is winning: just jump to that losing $G_y$.

If $B_x$ is false, then jumping never helps, and the game at value $x$ is pure parity:

$$W(x,0)=\text{lose},$$

and for $r>0$,

$$W(x,r)=\neg W(x,r-1).$$

Therefore:

$$G_x = W(x,c_x-1)$$

is losing exactly when:

$$c_x \text{ is odd and there is no reachable larger losing } G_y.$$

That DP is already enough, but it collapses into a much simpler condition.

The collapse

Arseniy can make Egor win if either of these happens:

1. Some frequency is even

If $c_x$ is even, then after Arseniy removes one $x$, there are $c_x-1$ copies left, which is odd.

If no useful jump exists, Egor just takes equal values and wins by parity. If a useful jump exists, even better. So any even positive frequency immediately gives YES.

2. Two distinct present values are within distance $k$

Suppose there are present values $x<y$ with

$$y-x\le k.$$

If $G_y$ is winning, Arseniy simply chooses $y$.

If $G_y$ is losing, Arseniy chooses $x$, and Egor jumps to $y$, giving Dabir a losing state.

Either way, YES.

When is the answer NO?

Only when both nice things fail:

• every present value has odd frequency;
• every two distinct present values differ by more than $k$.

Then after Arseniy chooses any value $x$, Egor only has an even number $c_x-1$ of equal values to play with and cannot jump anywhere. Egor loses. Brutally simple.

So the algorithm is:

1. Count frequencies.
2. If any positive frequency is even, answer YES.
3. Otherwise, scan present values in sorted order. If two adjacent present values differ by at most $k$, answer YES.
4. Else answer NO.

Adjacent values are enough because if any two present values are close, some adjacent pair in sorted order is also close.

Complexity

For each test case we scan values from $1$ to $n$:

$$O(n)$$

time and

$$O(n)$$

memory. Across all tests, this is

$$O\left(\sum n\right),$$

which easily fits.