N-MEX (Constructive Version)

Observation 1: count the missing numbers

At prefix $i$, $a_i$ is the $(n-i+1)$-mex. So exactly $n-i$ numbers smaller than $a_i$ are missing, and $a_i$ itself is missing.

There are only $a_i$ numbers below $a_i$, hence

$$a_i \ge n-i.$$

Also, after $i$ insertions, at most $i$ distinct numbers below $a_i$ can be present. The number present below $a_i$ must be

$$a_i-(n-i),$$

so it cannot exceed $i$. Therefore

$$a_i \le n.$$

Thus every valid sequence satisfies

$$n-i \le a_i \le n.$$

With $0$-indexed code, this is $n-i-1\le a_i\le n$.

Observation 2: $a$ cannot go up

From prefix $i-1$ to prefix $i$, we add one number, while the requested missing rank decreases by $1$:

$$n-i+2 \to n-i+1.$$

Removing at most one missing number cannot make this lower rank point to a larger value. So we also need

$$a_i\le a_{i-1}.$$

Define a fake value $a_0=n$. Before inserting anything, the $(n+1)$-mex of the empty set is $n$, so this makes the first real step fit the same rule.

Construction

Call a value forbidden if it appears in $a$. We never output forbidden values, because if $a_j=x$ for some $j$, then $x$ must still be missing at prefix $j$. Printing it would instantly nuke the solution. Very efficient, very wrong.

Maintain a pointer from $n-1$ down to $0$, skipping forbidden values.

For each $i$:

• If $a_i<a_{i-1}$, output $10^9$.
• If $a_i=a_{i-1}$, output the current largest unused non-forbidden value.

Why this works:

• On a strict drop, outputting $10^9$ changes nothing among $0,1,\dots,n$, so the missing list stays the same. Since the requested rank decreases by $1$, the answer drops to the previous relevant missing value.
• On an equal step, the rank decreases but the answer must stay the same, so we must remove one missing number below $a_i$. The pointer gives exactly such a value.

For the clean invariant, after processing prefix $i$, exactly

$$a_i-(n-i)$$

inserted useful values are below $a_i$. Therefore the number of missing values below $a_i$ is

$$a_i-\bigl(a_i-(n-i)\bigr)=n-i.$$

And $a_i$ itself is missing because it is forbidden. Hence $a_i$ is exactly the $(n-i+1)$-mex.

The pointer never runs out: every strict drop introduces one new forbidden value below $n$, and every non-drop step consumes one non-forbidden value. The counts match perfectly. Cute little bookkeeping trick, no wizardry.

Complexity

Each value is skipped by the pointer at most once, so the whole construction is linear:

$$O(n)$$

per test case, and

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

over all test cases. Memory usage is $O(n)$.

Cross-checked against the official Codeforces editorial: https://codeforces.com/blog/entry/151886.