짐 정리

일렬로 놓인 N개의 짐칸에 서로 다른 무게의 짐이 하나씩 들어 있다. 짐칸을 앞에서부터 무게가 작은 순서대로 정리하려고 한다. 한 번의 작업에서는 두 짐의 위치를 서로 바꾸며, 이때 필요한 힘은 두 짐의 무게의 합이다.

짐칸의 수와 현재 배치된 짐의 무게가 앞에서부터 차례대로 주어질 때, 짐칸을 정리하는 데 필요한 최소 힘을 구하라.

예를 들어, 무게가 10, 2, 8, 5인 네 개의 짐이 차례대로 놓여 있다고 하자. 무게 10인 짐과 무게 2인 짐을 서로 바꾸고, 이어서 무게 10인 짐과 무게 5인 짐을 서로 바꾸면 정리가 끝난다. 이때 필요한 총 힘은 <그림 1>처럼 (10+2) + (10+5) = 27이다.

<그림 1>

반대로 먼저 무게 2인 짐과 무게 5인 짐을 서로 바꾸고, 이어서 무게 10인 짐과 무게 2인 짐을 서로 바꾸어도 짐칸이 정리된다. 이 방법의 총 힘은 <그림 2>처럼 (2+5) + (10+2) = 19이다.

<그림 2>

첫째 줄에 짐칸의 수 N이 주어진다. 다음 N개의 줄에는 앞에서부터 각 짐칸에 놓인 짐의 무게가 하나씩 주어진다.

N은 1,000 이하의 자연수이고, 각 짐의 무게는 10,000 이하의 자연수이다. 모든 짐의 무게는 서로 다르다.

첫째 줄에 짐칸을 정리하는 데 필요한 최소 힘을 출력한다.