Prvo ćemo preračunati niz ~R~, čiji ~i~-ti član označava najdesnije pojavljivanje elementa ~i~ u nizu ~S~ ~(R[i] = \max_{j\leq n} S[j] = i)~.

Iteriraćemo po poziciji pojavljivanja prvog elementa ~B~ u paternu ~A B A B~ s leva na desno. Pretpostavimo da se trenutno nalazimo na poziciji ~i~ i da je ~S[i] = Y~. Za drugo pojavljivanje elementa ~Y~ u paternu ~A B A B~ koristićemo element na poziciji ~R[Y]~ (u slučaju ~R[Y] = i~ ovu poziciju nećemo dalje razmatrati). Nema potrebe uzimati neko ranije pojavljivanje vrednosti ~Y~ posle pozicije ~i~ jer na taj način samo smanjujemo prostor za uzimanje prve vrednosti u paternu.

Sada smo zadatak sveli na pronalaženje najmanje vrednosti ~X~ ~(X \neq Y)~, takve da se ~X~ pojavljuje u intervalu ~[1, i - 1]~ i u intervalu ~[i+1, R[Y] -1]~. Ovaj problem možemo rešiti pomoću segmentnog stabla:

• Izračunajte još jedan pomoćni niz ~D~, gde u ~i~-tom trenutku vrednost ~D[X]~ predstavlja prvo desno pojavljivanje elementa ~X~ u nizu ~S~ nakon pozicije ~i~. Ako se element ~X~ nije pojavio do pozicije ~i~ ili ne postoji element ~X~ nakon pozicije ~i~, tada je ~D[X] = N + 1~. Nama je rešenje za trenutnu poziciju najmanje ~X~ takvo da ~D[X] < R[Y]~ i ~X \neq Y~.

Za navedeni niz možemo napraviti minimum segmentno stablo (svaki čvor pamti minimum za sve elemente ~D~ u odgovarajućem intervalu). Izvršićemo šetnju po stablu dok ne dođemo do lista koji nam predstavlja rešenje za trenutnu poziciju. Pod šetnjom podrazumevamo sledeći proces:

• Počećemo iz korena segmentnog stabla
• Ako trenutni čvor obuhvata interval [l, r], videćemo vrednost u njegovom levom detetu (ta vrednost predstavlja minimum u intervalu ~[l, \frac{l+r}{2}])~, ako je ona manja od ~R[Y]~ idemo u levo dete, inače idemo u desno.
• Ako smo stigli do lista, završili smo proces i našli smo rešenje za tu poziciju (ako smo stgli do ~N+1~ lista onda ne postoji rešenje).

Napomena: Treba biti pažljiv prilikom šetnje zbog uslova ~(X \neq Y)~, postoji više načina kako to može da se reši.

Nakon pomeranja sa pozicije ~i~ na poziciju ~i+1~ u nizu ~S~, potrebno je promeniti jednu vrednost u nizu ~D~ ~(D[S[i]])~, ujedno promeniti odgovarajuću vrednost i u segmentnom stablu.

Asimptotska složenost navedenog rešenja ~O(n log n)~.

Zadatak je preuzet sa ~\texttt{Moscow}~ ~\texttt{Autumn}~ ~\texttt{Workshop}~ ~\texttt{2019}~ ~\texttt{Day}~ ~\texttt{1}~, takmičenje ~\texttt{Welcome}~ ~\texttt{Contest}~ ~\texttt{from}~ ~\texttt{Asia}~.