Задача . A. Паша и шашлыки

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

Для этого у Паши есть план, а именно перестановка p и последовательность b₁, b₂, ..., b_n, состоящая из нулей и единиц. Каждую секунду Паша перекладывает шампур на месте i на место p_i, и, если b_i равно 1, то разворачивает его. Таким образом он надеется, что все шампуры побывают на всех позициях, каждый в двух положениях.

К сожалению, не всякая перестановка p и последовательность b подходят для плана Паши. Какое минимальное суммарное количество элементов в перестановке p и элементов в последовательности b ему надо изменить, чтобы каждый шампур побывал во всех 2n положениях? При этом перестановка должна остаться перестановкой.

Пашу не беспокоит, если шампур примет одно и тоже положение несколько раз прежде, чем он закончит жарить шашлыки. Иными словами, перестановка p и последовательность b ему подходят, если существует такое число k (k ≥ 2n), что после k секунд каждый шампур побывает в каждом из 2n положений.

Можно показать, что некоторая подходящая перестановка p и последовательность b существуют для любого n.