Cow Sorting#1091
Farmer John has (1 \leq N \leq 10000) cows lined up for evening milking. Each cow has a unique grumpiness level ranging from to . Since grumpier cows are more likely to damage the milking equipment, Farmer John wants to rearrange the cows so that cows with higher grumpiness come later in line (i.e., the cows are ordered in increasing order of grumpiness).
He can swap the positions of any two cows (not necessarily adjacent). Swapping two cows with grumpiness levels and takes X + Y units of time.
Help Farmer John determine the minimum total time required to reorder the cows in increasing order of grumpiness.
The first line contains a single integer .
The next lines each contain a single integer: the grumpiness level of the -th cow.
Output a single integer — the minimal total time required to reorder the cows in increasing order of their grumpiness.
Example 1
: Initial order.
: After swapping cows with grumpiness and (time = 1 + 3 = 4).
: After swapping cows with grumpiness and (time = 2 + 1 = 3).