아령 정렬

한 헬스장에는 무게가 모두 서로 다른 아령 (n)개가 걸려 있다.

이 아령들은 이용자가 찾기 쉽도록 원래 무게가 작은 것부터 큰 것까지 순서대로 걸려 있어야 한다. 하지만 사람들이 운동을 마친 뒤 아무 위치에나 다시 걸어 두기 때문에, 하루가 끝나면 순서가 뒤섞일 수 있다.

할 수 있는 작업은 이미 걸려 있는 아령 두 개를 골라 서로의 위치를 바꾸는 것뿐이다. 한 번 작업할 때 드는 힘은 선택한 두 아령의 무게의 합이다. 아령이 매우 무겁기 때문에 한 번 작업을 마칠 때마다 반드시 쉬어야 하며, 따라서 한 번의 작업에서는 두 아령의 위치를 바꾸는 일만 할 수 있다.

현재 아령이 걸려 있는 순서가 주어졌을 때, 아령들을 무게가 작은 것부터 큰 것까지 다시 정렬하는 데 필요한 최소 힘을 구하라.

첫째 줄에 아령의 개수 (n) ((1 \le n \le 100,000))이 주어진다.

둘째 줄에는 현재 걸려 있는 순서대로 아령의 무게 (n)개가 주어진다. 각 무게는 서로 다른 자연수이며 (2^{30}) 이하이다. 입력은 정답이 (2^{31}-1) 이하가 되도록 주어진다.

필요한 힘의 최솟값을 출력한다.