7. Railway carriage permutation

Поезд «Голубая стрела» состоит из N вагонов, которые прицеплены к паровозу и пронумерованы по возрастанию: паровоз, вагон 1, вагон 2 и т.п. Порядок вагонов существенен: чем ближе к паровозу, тем теплее (а дело происходит суровой итальянской зимой).

Итак, суровой итальянской зимой поезд подъехал к разъезду. И выяснилось, что дальше «Голубой стреле» не нужно, а нужно в обратную сторону. Требуется развернуть поезд, сохранив при этом порядок следования вагонов (во время манёвров этот порядок, естественно, можно ненадолго нарушать). Бригада поезда может сцеплять и расцеплять вагоны, перегонять в любое место паровоз, при этом паровоз может тянуть за собой или толкать впереди себя любое количество вагонов. Какое наименьшее количество манёвров придётся для этого совершить поезду? Под манёвром понимается перемещение поезда между двумя остановками для сцепления/расцепления вагонов или смены направления на противоположное. Предполагается, что на любом из двух путей разъезда «Голубая стрела» может разместиться полностью.

Ввод: натуральное число N < 100 – количество вагонов поезда

Вывод: M – минимальное возможное количество манёвров для достижения требуемого положения