Posmatrajmo $mex$ vrednosti prefiksa. Označimo $i$-tu od njih sa $pref[i]$. Primetimo da te vrednosti moraju da budu neopadajuće, inače nema rešenja. Takođe, primetimo da, kako su te vrednosti $mex$-ovi $N$ brojeva, one moraju biti manje od $N+2$. Neka je $pref[i] \neq pref[i-1]$. Tada očigledno mora da važi $A[i] = pref[i-1]$, jer se vrednost $pref[i-1]$ ne pojavljuje u prefiksu dužine $i-1$, a pojavljuje se u prefiksu dužine $i$. Reći ćemo da smo onda fiksirali pojavljivanje vrednosti $pref[i-1]$ u prefiksu na poziciji $i$. Takođe, primetimo da vrednosti u intervalu $[pref[i-1]+1,pref[i]]$, moraju postojati u prefiksu dužine $i-1$. Slično ponovimo i za sufikse.

Primetimo sada da za svaku vrednost manju od $N$ koja se pojavljuje u našem nizu imamo u kom prefiksu i u kom sufiksu ona mora da se pojavi. Neka je najveći indeks do kojeg neka vrednost mora da se pojavi da bi uslovi $mex$-a prefiksa bili ispunjeni $l[i]$, a najmanji indeks za sufiks $r[i]$. Neka je dodatno $l[i]=0$, ukoliko je pojavljivanje te vrednosti u prefiksu fiksirano, a $r[i]=N+1$, ukoliko je pojavljivanje te vrednosti u sufiksu fiksirano. Posmatrajmo za svaku vrednost $i$ za koju nismo ispunili uslove pojavljivanja u prefiksu i u sufiksu (vrednosti za koje ti uslovi jesu ispunjeni su one za koje su fiksirana oba pojavljivanja ili one za koje jedno fiksirano pojavljivanje ispunjava uslove drugog) sledeće slučajeve:

• Pojavljivanje u prefiksu nije fiksirano i $l[i] < r[i]$. Tada ovu vrednost postavimo na najmanju poziciju u nizu na kojoj nije postavljena neka druga vrednost.
• Pojavljivanje u sufiksu nije fiksirano i $l[i] < r[i]$. Tada ovu vrednost postavimo na najveću poziciju u nizu na kojoj nije postavljena neka druga vrednost.
• Pojavljivanje nije fiksirano ni u prefiksu ni u sufiksu i $r[i] \leq l[i]$. Tada postavimo vrednost na bilo koju poziciju u intervalu $[l[i],r[i]]$, koja nije zauzeta. Ukoliko takva pozicija ne postoji, postavimo tu vrednost na najmanju poziciju koja nije zauzeta i najveću poziciju koja nije zauzeta.

Možemo da primetimo da će vrednosti $l[i]$ biti rastuće, a vrednosti $r[i]$ opadajuće. Zbog toga, kada $l[i] < r[i]$, optimalno je postaviti vrednosti na najmanju i najveću poziciju. Ukoliko je $r[i] \leq l[i]$, možemo da primetimo da za svaku vrednost $j$, za koju $i < j$ i za koju $r[j] \leq l[j]$, važi da $r[j] \leq r[i] \leq l[i] \leq l[j]$, tj. intervali će biti ugnježdeni. Zbog toga možemo na pohlepan način da postavljamo vrednosti u tom intervalu. Takođe, primetimo da postavljanje vrednosti na najmanje i najveće pozicije ne remeti postavljanje u intervale, jer ukoliko bi zbog postavljanja vrednosti na najmanju poziciju neki interval ceo bio zauzet, onda bi on, zbog uslova da $l[i]$ raste bio zauzet gde god mi postavili tu vrednost.

Konačno, ukoliko na nekoj poziciji u nizu nismo postavili vrednost, na tu poziciju možemo da postavimo proizvoljnu vrednost veću od $N+1$.