Train Car Reordering

A historic train station uses a pivoting bridge that can hold at most two train cars. When the bridge rotates 180° it swaps the positions of two adjacent train cars. This operation is used to reorder the cars. Given an initial sequence of train cars (identified by unique numbers), determine the minimum number of steps (i.e. adjacent swaps) needed to arrange the cars in increasing order by their numbers.

Note: The minimum number of adjacent swaps required to sort the sequence is exactly the number of inversions in the permutation. An inversion is a pair (i, j) such that i < j and A[i] > A[j].

inputFormat

The first line contains an integer n (the number of train cars). The second line contains n space-separated integers representing the initial order of the train cars.

outputFormat

Output a single integer, the minimum number of swapping steps required to sort the train cars in increasing order.

sample

3
3 1 2

2