Dumbbell Sorting

A gym has (n) dumbbells, and all of their weights are different.

For convenience, the dumbbells should be hung from lightest to heaviest. However, after people use them, they may hang them back in arbitrary positions, so the order can be mixed up by the end of the day.

You may perform only one kind of operation: choose two dumbbells that are already hanging and swap their positions. The effort required for one such operation is the sum of the two selected weights. Because the dumbbells are heavy, you must rest after each operation, so a single operation can only swap two dumbbells.

Given the current order of the dumbbells, compute the minimum total effort needed to restore the order from lightest to heaviest.

The first line contains (n) ((1 \le n \le 100,000)), the number of dumbbells.

The second line contains (n) weights in the order in which the dumbbells are currently hanging. All weights are distinct positive integers not greater than (2^{30}). The input is guaranteed so that the answer is at most (2^{31}-1).

Print the minimum total effort required.