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}$.