Cow Sorting

Farmer John's $N$ cows ($1 \le N \le 10{,}000$) are lined up to be milked in the evening. Each cow has a unique grumpiness level in the range $1 \ldots 100{,}000$. Since grumpy cows are more likely to damage FJ's milking equipment, FJ would like to reorder the cows in line so that they stand in increasing order of grumpiness.

During this process, the places of any two cows (not necessarily adjacent) can be interchanged. Since grumpy cows are harder to move, it takes FJ a total of $X + Y$ units of time to exchange two cows whose grumpiness levels are $X$ and $Y$.

Help FJ compute the minimum total time required to reorder the cows into increasing order of grumpiness.

• Line $1$: A single integer $N$.
• Lines $2 \ldots N+1$: Line $i+1$ contains a single integer, the grumpiness of cow $i$.

• A single line with the minimum time required to reorder the cows into increasing order of grumpiness.

Suppose the cows stand in grumpiness order $2\ 3\ 1$. First interchange the cows with grumpiness $3$ and $1$ at a cost of $3 + 1 = 4$, giving $2\ 1\ 3$. Then interchange the cows with grumpiness $1$ and $2$ at a cost of $1 + 2 = 3$, giving $1\ 2\ 3$, for a total cost of $7$.