35110번 - Swap, then record

길이 $N$인 수열 $A$가 주어진다. 수열의 모든 원소의 값은 서로 다르며, 당신은 아래의 연산을 원하는 만큼 수행하여 수열 $A$를 오름차순으로 정렬해야 한다.

• $1 \leq i < j \leq N$인 $i$, $j$를 골라 $A_i, A_j$의 자리를 바꾸고, $X = \min(A_i, A_j)$, $Y = \max(A_i, A_j)$에 대해 기록에 정수 쌍 $(X, Y)$를 추가한다. 동일한 정수 쌍이 이미 기록되어 있다면 추가하지 않는다.

연산 과정에서 기록에 정수 쌍 $(X, Y)$를 추가할 때마다 $Y-X$의 비용이 발생한다고 할 때, 수열 $A$를 오름차순으로 정렬하면서 발생하는 비용의 합의 최솟값을 구해보자.

첫 번째 줄에 수열 $A$의 길이 $N$이 주어진다. $(2 \leq N \leq 200\,000)$

두 번째 줄에 수열 $A$의 원소 $A_1,A_2,\dots,A_N$이 공백으로 구분되어 주어진다. $\left(1 \leq A_i \leq 10^9\right)$

수열 $A$의 모든 원소의 값은 서로 다르다.

수열을 오름차순으로 정렬하면서 발생하는 비용의 합의 최솟값을 출력한다.