Problem najdalszego mniejszego (prawego) sąsiada w permutacji jak sama nazwa wskazuje polega na znalezieniu sąsiadów którzy będą spełniali następujące wymagania:

- Sąsiad musi być mniejszy od aktualnego elementu
- Sąsiad musi być po prawej
- Musi być to ostatni sąsiad spełniający te wymagania

Dodatkowo wiemy, że takich sąsiadów będziemy szukać w permutacji, czyli będziemy mieć liczby od 1 do n bez powtórzeń.

Sprawdźmy jak będzie to wyglądać dla następującej listy:

1	3	2	4

Naszym wynikiem będzie taka tablica:

1	3	3	4

Wytłumaczenie przykładu:
Zaczynamy od 1, nie ma po prawej mniejszych liczb, więc najdalszym mniejszym sąsiadem będzie ona sama.
Po prawej od 3 mamy 2, a następną liczbą byłoby 4, które jest większe, więc najdalszym mniejszym sąsiadem jest 2 na pozycji trzeciej
W przypadku 2 oraz 4 jest podobnie jak z 1, czyli one same są tymi sąsiadami

Algorytm liniowy:
Podczas przechodzenia przez permutację dla której chcemy uzyskać rozwiązania tworzymy listę zawierającą odwrotność permutacji, np. dla:

3	4	2	1

Będziemy tworzyć taką tablicę:

4	3	1	2

Dzięki niej możemy w łatwy sposób sprawdzić:
- Dla danej liczby jej położenie w tablicy wejściowej
- Czy napotkaliśmy już daną liczbę - możemy to zrobić inicjalizując tablicę wartością która nie pojawi się w wejściu

Jeżeli są mniejsze jeszcze nienapotkane liczby idziemy dalej, bo nie będzie to najdalszy sąsiad
Jeżeli nie ma już mniejszych nienapotkanych liczb to wiemy że jest to najdalszy mniejszy sąsiad dla samej siebie oraz każdej już napotkanej liczby większej od siebie

Powyższy algorytm napisany w Pythonie:

def algo(A):
        m = 1
        pozycja = [0] * n
        najd_prawy = [0] * n

        for i in range(1, len(A)+1):
            pozycja[A[i-1]-1] = i
            while (m <= n) and (pozycja[m-1] != 0):
                najd_prawy[pozycja[m-1]-1] = i
                m = m + 1