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~.