최소 비용으로 추 정렬하기

서로 무게가 모두 다른 추 n개가 왼쪽에서 오른쪽으로 한 줄로 놓여 있다. 현재 순서는 무게와 관계없이 임의로 정해져 있다.

두 추의 위치를 서로 바꾸는 연산만 사용할 수 있다. 무게가 각각 X와 Y인 두 추를 바꾸면 X + Y만큼의 에너지가 든다.

모든 추가 왼쪽에서 오른쪽으로 무게의 오름차순이 되도록 정렬하려고 한다. 필요한 에너지의 합이 최소가 되도록 정렬할 때, 그 최소 에너지를 구하라.

첫째 줄에 추의 개수 n이 주어진다. (1 <= n <= 100,000)

이후 n개의 줄에는 현재 왼쪽에 놓인 추부터 차례대로 각 추의 무게가 주어진다. (1 <= 추의 무게 <= 1,000,000)

모든 추의 무게는 서로 다르다.

추를 오름차순으로 정렬하는 데 필요한 최소 에너지를 첫째 줄에 출력한다.

무게가 2, 3, 1 순서로 놓인 경우, 먼저 무게 3인 추와 무게 1인 추를 바꾸고, 이어서 무게 2인 추와 무게 1인 추를 바꾸면 총 에너지는 7이 된다.