Suppose is a MEX-correct sequence. For all , it is easy to see that is non-decreasing. So the constraint that basically says that should be “roughly” non-decreasing as well. Further analysis shall formalize this idea.
Let us denote for each position . Then the value of and hence the choice of is determined by the elements in .
Let us start by considering values that may take, with being an empty set.
If , then which satisfies our constraint. Then and let us consider possible values of :
. Then we have . Further, which is unchanged from . Similarly, it is always possible to append to the sequence so that and .
. Then we have . Further, . Similarly, we can see for , it is always possible to append to the sequence to get .
. Then we have . Further, . In this case, we cannot append because that would lead to . We cannot append either since that way remains and is at least from . From this point on, the only possible values to append to the sequence are and . Similarly, for , where a “jump” has taken place at some previous position, the only possible values of to append to the sequence are and .
No other values of are possible.
If , then . It is obvious that in this case we can only repeatedly append to the sequence with no other values possible.
No other values of are possible.
As we can see, there are three patterns of a valid MEX-correct sequence: