A museum shelf holds stones with distinct weights weights, left to right. A curator may
swap any two stones (not only neighbours); swapping stones of weights a and b costs
a + b. Return the minimum total cost to put the shelf in increasing order of weight.
An empty or already sorted shelf costs 0.
Examples
Input: weights = [3, 2, 1]
Output: 4
Explanation: swap 3 and 1 once, for 3 + 1 = 4.
Input: weights = [1, 8, 9, 7, 6]
Output: 41
Explanation: 8, 9, 7 and 6 form one loop. The best plan using only those four costs 42; borrowing
the 1 is cheaper: swap 1 and 6, fix the other three stones using the 1, then swap it back, 41 in total.
Constraints
0 <= len(weights) <= 10**51 <= weights[i] <= 10**6, all different- An O(n log n) solution is expected.
Goals
- Split the rearrangement into independent cycles by comparing with the sorted order
- Price each cycle two ways: with its own lightest stone, or with the lightest stone overall
- Use a dictionary from value to sorted position instead of repeated searching