P6193 [USACO07FEB] Cow Sorting G

Farmer John has $n$ cows ($1 \leq n \leq 10^5$) standing in a line. Each cow has a “grumpiness” level in the range $1 \ldots 10^5$, and no two cows have the same grumpiness value. Since grumpier cows are more likely to damage FJ’s milking equipment, FJ wants to rearrange the cows so that they are ordered by increasing grumpiness. During this process, the positions of any two cows (not necessarily adjacent) can be swapped. Since grumpy cows are hard to move, FJ needs a total of $X + Y$ units of time to swap two cows whose grumpiness levels are $X$ and $Y$. Please help FJ compute the minimum time needed to sort the cows in increasing order of grumpiness.

The first line contains one integer: $N$. The next $N$ lines each contain one integer $a_i$, representing the grumpiness value of the $i$-th cow.

Output the minimum time needed to sort all cows in increasing order of grumpiness.

Translated by ChatGPT 5