시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB55626422558.140%

문제

n개의 추가 여러분 앞에 왼쪽에서 오른쪽까지 일렬로 놓여 있다. 추의 무게는 모두 다르며, 추가 놓여 있는 순서는 무게와 무관한 임의의 순서이다.

이 추를 무게에 따라 왼쪽에서 오른쪽으로 오름차순 정렬하고자 한다. 정렬을 위해서는 두 개의 추를 들어서 서로의 위치를 바꾸는 방법을 쓰는데, 당연히 무거운 추일수록 드는 데 많은 에너지가 필요할 것이다. 무게가 각각 X와 Y인 추의 위치를 서로 바꾼다고 하면, X+Y만큼 에너지가 소모된다고 하자. 여러분이 해야 할 일은 추를 정렬하는 데에 최대한 적은 에너지를 사용하도록, 추의 정렬 계획을 세우는 것이다.

입력

첫째 줄에 추의 개수 n이 주어진다. (1 ≤ n ≤ 100,000) 다음 n개의 줄에는 왼쪽에 놓여 있는 추의 것부터 순서대로 무게가 주어진다. (1 ≤ 추의 무게 ≤ 1,000,000)

출력

첫 줄에 필요한 최소의 에너지를 출력하면 된다.

예제 입력 1

3
2
3
1

예제 출력 1

7

힌트

맨 처음에 무게 3, 무게 1의 추를 서로 교환한다. 이어서 무게 2, 무게 1의 추를 서로 교환하면 된다.