Description

Beside an old-fashioned railway station, there is a bridge whose deck can rotate horizontally around a pier at the center of the river. A station employee discovered that the bridge can accommodate at most two train carriages at a time. By rotating the bridge 180 degrees, the positions of two adjacent carriages can be swapped, and this method can be used to rearrange the order of the carriages.

Thus, he was responsible for using this bridge to sort the incoming carriages in ascending order by their carriage numbers. After his retirement, the railway station decided to automate this task, with one crucial step being the development of a program that takes the initial carriage order as input and calculates the minimum number of rotations required to sort the carriages.

Input Format

There are two lines of input. The first line contains the total number of carriages ( N ) (not exceeding 10,000), and the second line contains ( N ) distinct numbers representing the initial order of the carriages.

Output Format

A single number indicating the minimum number of rotations required.

4
4 3 2 1

6