Mix Mex Max

The key is to stop trying to “fill” the array first. The condition is local, so we should first understand what a valid length-$3$ block can even look like.

Take any triple $(x,y,z)$.

Let

$$mn=\min(x,y,z), \qquad mx=\max(x,y,z).$$

We need:

$$\operatorname{mex}(x,y,z)=mx-mn.$$

Classifying one triple

There are two cases.

Case 1: the triple does not contain $0$.

Then the smallest missing non-negative integer is $0$, so:

$$\operatorname{mex}(x,y,z)=0.$$

So we need:

$$mx-mn=0.$$

That means $mx=mn$, so all three values are equal. Also, since the triple does not contain $0$, that equal value must be positive.

So triples like $(1,1,1)$, $(5,5,5)$, $(100,100,100)$ work.

Case 2: the triple contains $0$.

Then the MEX is positive, because $0$ is already present.

Also, since all values are non-negative and $0$ is present, we have:

$$mn=0.$$

So the right side becomes:

$$mx-mn=mx.$$

The condition would require:

$$\operatorname{mex}(x,y,z)=mx.$$

But $mx$ is literally one of the values in the triple. The MEX is supposed to be a value that is missing. So this is impossible. That assumption crashes immediately. Beautifully rude math.

Therefore, the only valid triples are:

$$(c,c,c) \quad \text{where } c>0.$$

What this means for the whole array

Every consecutive triple must be valid. So every consecutive triple must contain three equal positive values.

That forces the whole completed array to be one constant positive value.

For example, from the triple $(a_1,a_2,a_3)$ we get:

$$a_1=a_2=a_3.$$

From $(a_2,a_3,a_4)$ we get:

$$a_2=a_3=a_4.$$

So $a_4$ equals the same value too. Continuing this, every position must equal the same positive number.

So the problem becomes very simple:

Can all known values already fit into one positive constant array?

That is true exactly when:

1. No known value is $0$.
2. All known non-$-1$ values are equal.

If every element is $-1$, we can choose any positive value, like $1$, for all positions.

If the known values are all $7$, fill every missing spot with $7$.

If there is a $0$, impossible.

If there are two different positive known values, impossible.

So for each test case, scan the array and keep the first known value. Every other known value must match it, and it must be positive.