Beautiful Intervals

Think in positions, not values.

Let $pos_x$ be the position of value $x$ in the permutation. For any interval $I$, we have:

• $\operatorname{mex}(I)=0$ iff $I$ does not contain $pos_0$.
• $\operatorname{mex}(I)=1$ iff $I$ contains $pos_0$ but does not contain $pos_1$.
• $\operatorname{mex}(I)=2$ iff $I$ contains both $pos_0$ and $pos_1$, but does not contain $pos_2$.

That already tells us almost the whole problem. The interval values are just wearing fake mustaches; the positions are what matter.

A Universal Upper Bound: We Can Always Make Mex $2$ Missing

Place the values so that $2$ lies between $0$ and $1$ in the array, for example:

$$0, 2, 1$$

at three consecutive positions.

Any contiguous interval containing both $0$ and $1$ must also contain everything between them, including $2$. Therefore no interval can contain $0$ and $1$ while excluding $2$.

So mex $2$ never appears in $M$.

That means the optimal answer is always one of $0,1,2$. Nice. We only need to check whether we can do better than $2$.

When Is Mex $0$ Missing?

Mex $0$ appears if some interval does not contain $0$.

So mex $0$ is missing iff every interval contains $0$.

That is possible exactly when all intervals have a common point. If

$$L = \max l_i, \qquad R = \min r_i,$$

then the common intersection is nonempty iff $L \le R$.

If this happens, place $0$ anywhere in $[L,R]$ and fill the rest arbitrarily. Then every interval contains $0$, so no interval has mex $0$, and the minimum possible $\operatorname{mex}(M)$ is $0$. You can't beat zero, obviously.

When Is Mex $1$ Missing?

Now suppose mex $0$ is impossible to remove. Then no matter where we place $0$, some interval misses it, so mex $0$ appears.

To make $\operatorname{mex}(M)=1$, we need mex $1$ to be missing. Mex $1$ appears when an interval contains $0$ but misses $1$.

So we need:

Every interval containing $0$ must also contain $1$.

How can we force that?

Put $0$ at position $i$ and $1$ at position $i+1$.

An interval containing $i$ but not $i+1$ must end exactly at $i$. Therefore, if no interval ends at $i$, then every interval containing $0$ also contains $1$.

Similarly, put $1$ at position $i$ and $0$ at position $i+1$.

An interval containing $i+1$ but not $i$ must start exactly at $i+1$. Therefore, if no interval starts at $i+1$, then every interval containing $0$ also contains $1$.

So scan every adjacent pair $(i,i+1)$:

• if no interval ends at $i$, set $p_i=0$, $p_{i+1}=1$;
• else if no interval starts at $i+1$, set $p_i=1$, $p_{i+1}=0$.

If either case works, mex $1$ is missing, and since mex $0$ is already unavoidable, this is optimal.

If Mex $0$ and Mex $1$ Both Fail

Then the answer must be $2$.

Use the universal construction:

$$p_1=0,\quad p_2=2,\quad p_3=1.$$

Then mex $2$ is missing because every interval containing positions $1$ and $3$ also contains position $2$.

We also need mex $0$ and mex $1$ to appear:

• Mex $0$ appears because the common intersection of all intervals is empty, so some interval misses position $1$.
• Mex $1$ appears because if the mex $1$ scan failed, then in particular some interval ends at $1$. The only possible such interval is $[1,1]$, which contains $0$ and misses $1$.

So $0,1 \in M$ and $2 \notin M$, giving $\operatorname{mex}(M)=2$.

Algorithm

For each test case:

1. Read all intervals.
2. Track:
   • start[x]: whether some interval starts at $x$,
   • finish[x]: whether some interval ends at $x$,
   • the common intersection $[\max l_i, \min r_i]$.
3. If the common intersection is nonempty, place 0 there.
4. Otherwise, scan adjacent pairs:
   • if finish[i] == false, place 0,1 at i,i+1;
   • else if start[i+1] == false, place 1,0 at i,i+1.
5. If neither worked, place 0,2,1 at positions 1,2,3.
6. Fill all remaining positions with the unused values in increasing order.

Correctness Proof

We prove the construction minimizes $\operatorname{mex}(M)$.

First, for any interval, mex $k$ depends only on whether the interval contains the positions of $0,1,\dots,k$. In particular, mex $0$ depends only on $0$, mex $1$ only on $0$ and $1$, and mex $2$ only on $0,1,2$.

If all intervals share a common point and we put $0$ there, every interval contains $0$. Thus no interval has mex $0$, so $\operatorname{mex}(M)=0$. This is optimal.

If the intervals do not share a common point, then for every possible position of $0$, at least one interval misses it. That interval has mex $0$. Therefore mex $0$ is unavoidable, and the answer cannot be $0$.

For mex $1$ to be missing, every interval containing $0$ must also contain $1$.

If we place $0$ at $i$ and $1$ at $i+1$, this condition fails exactly when some interval ends at $i$. So if no interval ends at $i$, mex $1$ is missing.

If we place $0$ at $i+1$ and $1$ at $i$, this condition fails exactly when some interval starts at $i+1$. So if no interval starts at $i+1$, mex $1$ is missing.

Conversely, suppose mex $1$ can be missing with $0$ at position $x$ and $1$ somewhere else. If $1$ is to the right of $x$, then no interval can end at $x$, or that interval would contain $0$ and miss $1$. Then the adjacent placement $(0,1)$ at $(x,x+1)$ would also work. If $1$ is to the left of $x$, then no interval can start at $x$, and the adjacent placement $(1,0)$ at $(x-1,x)$ would work. Therefore the scan finds a mex-$1$ construction iff one exists.

If the scan succeeds, mex $0$ is unavoidable and mex $1$ is missing, so the answer is optimally $1$.

If the scan fails, mex $1$ is impossible to remove. Then we use positions $1,2,3$ as $0,2,1$. Any interval containing both $0$ and $1$ must contain $2$, so mex $2$ is missing. Since mex $0$ and mex $1$ are both unavoidable, the resulting mex of $M$ is exactly $2$, which is optimal.

Therefore the algorithm always outputs an optimal permutation.

Complexity

Everything is one pass over intervals plus one pass over positions:

$$O(n+m)$$

per test case.