Cow Sorting

Interview

Time limit1sMemory limit128 MB

Summary

Rearrange a permutation into sorted order by swapping any two elements at a cost equal to their sum, minimizing the total cost.

Level: Medium7 of 10
Topics: Greedy, Sorting, Math, Implementation
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Hint

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$ .

Examples4

Example 1
Input
```
3
2
3
1
```
Expected output
```
7
```
Example 2
Input
```
1
5
```
Expected output
```
0
```
Example 3
Input
```
2
2
1
```
Expected output
```
3
```
Example 4
Input
```
5
1
2
3
4
5
```
Expected output
```
0
```