P1116 Carriage Reordering

Next to an old-style railway station there is a bridge whose deck can rotate horizontally around the pier at the center of the river. A station worker discovered that the bridge can hold at most two carriages. If the bridge is rotated by $180$ degrees, the positions of two adjacent carriages can be swapped. Using this method, the order of the carriages can be rearranged. He was responsible for rearranging incoming carriages in increasing order of their carriage numbers. After he retired, the station decided to automate this work. One important task is to write a program that, given the initial order of the carriages, computes the minimum number of steps needed to sort the carriages.

The input consists of two parts. The first line is the total number of carriages $N( \le 10000)$. The second line contains $N$ distinct integers representing the initial order of the carriages. （Note: In the testdata, these integers are not necessarily on a single line and may be split across multiple lines.）

Output a single integer, the minimum number of rotations.

Translated by ChatGPT 5