Shifted MEX

The operation adds one integer $x$ to every element. That means the whole array slides left or right on the number line, but its internal structure stays the same. Distances between values do not change.

Suppose after shifting, the MEX is at least $k$. Then the shifted array must contain

$$0,1,2,\ldots,k-1.$$

If an original value $a_i$ becomes $j$, then $a_i + x = j$, so $a_i = j - x$. Therefore, before the shift, the array must have contained

$$-x, -x+1, -x+2, \ldots, -x+k-1.$$

That is just a consecutive block of length $k$ in the original array.

So any achievable MEX $k$ requires the original array to contain $k$ consecutive distinct integers. Duplicates do not matter at all. They are dead weight for this problem.

Now go the other way. If the original array contains a consecutive block

$$y, y+1, \ldots, y+L-1,$$

then choose

$$x = -y.$$

After shifting, those values become

$$0,1,\ldots,L-1.$$

If this block is maximal, then $y+L$ is not present, so $L$ is not present after the shift. Thus the MEX is exactly $L$.

Therefore, the maximum possible MEX is exactly:

$$\text{length of the longest consecutive run of distinct values in } a.$$

Implementation is straightforward:

1. Sort the array.
2. Scan from left to right.
3. Ignore duplicates.
4. If the current distinct value is exactly previous value $+1$, extend the current run.
5. Otherwise, start a new run.
6. Track the maximum run length.

Edge cases:

• $n=1$: one value can always be shifted to $0$, so the answer is $1$.
• All duplicates: longest distinct run has length $1$.
• Negative numbers are totally fine; shifting can move them wherever needed.
• Huge values are fine too. We only compare adjacent sorted values, so long long keeps things clean.

Complexity per test case:

$$O(n \log n)$$

for sorting, and

$$O(1)$$

extra memory besides the array. Given the total $n \le 3000$, this is comfortably inside the limits. Like, not even sweating.