문제
어느 날 저녁, 농부 창호의 N(1≤N≤10,000)마리 소들은 우유를 짜기 위해서 줄서있다. 각각의 소들은 1이상 100,000까지의 서로 다른 뺀질거림 수치를 가지고 있다.
말을 잘 듣지 않는 소가 농부 창호의 우유짜는 기구를 망가뜨릴 확률이 좀 더 높기 때문에, 농부 철기는 소들을 뺀질거림 수치가 낮은 소부터 높은 순으로 새로이 줄을 세우려고 한다.
이 새로운 줄을 세우는 작업동안, 어떠한 임의의 두 소는 (꼭 인접해있지 않아도) 서로 교체될 수 있다.
X와 Y를 각각 교체하려는 소의 말안들음 수치라고 할 때, 말을 듣지 않는 소일수록 소의 자리를 움직이는 것도 좀 더 힘들기 때문에 농부 창호가 두 소를 교체하는데엔 X+Y의 시간이 걸린다.
소를 새로이 배열시키는 일에 필요한 최소의 시간을 계산해서 농부 창호를 도와주어라.
입력
첫 번째 줄에는 한 개의 정수 N이 입력된다.
두 번째 줄부터 N+1번째 줄에는 하나의 정수가 쓰여 있으며, i+1번째 줄에에 위치한 정수는 i번째 소의 뺀질거림 수치를 뜻한다.
출력
소들을 뺀질거림 수치를 기준으로 재 정렬하는데 드는 최소한의 시간을 출력하라.
예제1
입력
3
2
3
1
출력
7
출처
USACO 2007 February Gold