задача Футурама (3298 на informatics.mccme.ru)

Условие
Эта задача показалась мне довольно интересной. Тем более, что она имеет схожие черты с другой очень хорошей задачей D++.

Итак, суть сводится к тому, что нужно упорядочить массив с учетом того, что последние два элемента гарантированно находятся на своих позициях. Элементы, находящиеся на позициях i и j запрещается менять местами, если ранее уже совершались обмены i-ого и j-ого элементов.
Из условия нам дают понять как можно обменять два элемента местами, используя два последних элемента. Пусть нужно обменять элементы 3 и 4, находящихся на позициях i и j:

Теперь нужно вспомнить, что исходный набор чисел является перестановкой. Это позволяет разложить имеющуюся перестановку на циклы и уже в дальнейшем работать с каждым циклом отдельно.
Понятно, что если упорядочить элементы в каждом цикле, то исходная перестановка станет единичной, т.е. упорядоченной.
В представленном решении не нужно помнить о запрещенных позициях для обменов, т.к. они все будут осуществляться через последние два элемента. Для любого цикла перестановки справедлив один из случаев:
1) Длина цикла равна 1. Понятно, элемент цикла находится на “нужном” месте в перестановке и ничего делать не нужно
2) Длина цикла равна 2. В данном случае элементы цикла можно обменять местами по правилу изложенному выше
3) Длина цикла больше 2. Это самый сложный случай. Рассмотрим перестановку A = {5,6,4,1,3,2,7,8}:

Один из циклов перестановки С = 1-5-3-4-1. Поставим на свои элементы цикла, отличные от двух последних(1 и 4), т.е. 5 и 3. Это можно сделать с помощью промежуточных обменов с предпоследним элементом перестановки:

Получилась перестановка B = {7,6,3,1,5,2,4,8}. Теперь немного отвлечемся и рассмотрим перестановку
A’={4,6,3,1,5,2,7,8}. Она имеет цикл С’ = 1-4, в то время, как элементы 3 и 5 находятся на “своих” местах. Для упорядочивания цикла C’ можно воспользоваться п.2)
Перестановка B получается из перестановки A’ после первого же обмена. Поэтому чтобы закончить п.3) необходимо выполнить оставшиеся 3 обмена, чтобы обменять в перестановке A’ элементы 1 и 4:

После сортировки каждого цикла последние два элемента меняются местами, поэтому если количество циклов является нечетным, то на последней итерации необходимо их поменять местами.

Решение