Находим каждый элемент максимально возможной перестановки по очереди, начиная с самого первого. На его место может встать один из первых трех элементов. Берем из них максимальный, перемещаем его влево, если нужно. Считаем, сколько раз каждый из элементов уже был перемещен, и, опираясь на это, рассматриваем возможные варианты для элемента, который должен располагаться на следующей позиции и так далее. Заметим, что на каждом шаге будут израсходованы операции не более, чем у двух следующих элементов.