Minimum Cost Weight Sorting

There are n weights in a row from left to right. All weights have distinct masses, and their current order is arbitrary.

You may sort them only by swapping the positions of two weights. If the two weights have masses X and Y, the swap costs X + Y energy.

Sort all weights into increasing order from left to right. Compute the minimum possible total energy needed.

The first line contains the number of weights n. (1 <= n <= 100,000)

Each of the next n lines contains the mass of one weight, in the current order from left to right. (1 <= mass <= 1,000,000)

All masses are distinct.

Print the minimum total energy needed to sort the weights in increasing order.

For the order 2, 3, 1, first swap the weights with masses 3 and 1, then swap the weights with masses 2 and 1. The total energy is 7.