4E. Permute Intervals

Scenario 1: $n=3$, intervals $[1,3], [2,4], [3,5]$. Answer: $1\ 2\ 3$. Witness: $a = [1, 2, 3]$. Reading in permutation order: $a_1=1 \le a_2=2 \le a_3=3$. All values in range. The identity permutation works because the intervals already overlap in increasing order. All $6$ permutations are valid (intervals overlap heavily), but $1\ 2\ 3$ is lexicographically smallest.

Scenario 2: $n=3$, intervals $[5,7], [1,3], [2,4]$. Answer: $2\ 3\ 1$. Witness: $a = [5, 1, 2]$. Reading in permutation order: $a_2=1 \le a_3=2 \le a_1=5$. Interval $1$ has high values $[5,7]$ while intervals $2,3$ have low values, so index $1$ must come last. Only $2$ valid permutations exist: $2\ 3\ 1$ and $3\ 2\ 1$. Lexicographically smallest is $2\ 3\ 1$.

Scenario 3: $n=4$, intervals $[2,4], [1,3], [5,7], [1,2]$. Answer: $1\ 2\ 4\ 3$. Witness: $a = [2, 2, 5, 2]$. Reading in permutation order: $a_1=2 \le a_2=2 \le a_4=2 \le a_3=5$. Interval $3=[5,7]$ has high values so must come last. Among the remaining, index $4=[1,2]$ fits before $3$. There are $6$ valid permutations; $1\ 2\ 4\ 3$ is lexicographically smallest.