건강대학교 체력단련장에는 각기 다른 무게를 가진 N 개의 역기들이 고정대 위에 놓여있다. 아침에는 체력단련장 이용자들의 편의를 위하여 다음과 같이 무게순으로 정렬하여 둔다.(그림은 N 이 4 인경우)

하지만, 체력 단련장이 문을 닫을 때가 되면 , N 개의역기들은 무게 순과는 무관하게 어지럽게 놓여져 있다. 다음은 그러한 예 중의 하나이다.

체력단련장 관리자인 현우는 체력단련장의 문을 닫으면서 어지럽게 놓인 N 개의 역기들을 무게의 오름차순으로 정렬하는 일을 담당하고 있다. 역기의 무게가 만만치 않기 때문에 현우는 들어 옮기는 역기의무게의 합을 최소로 하여 정렬하고자 한다. 안전을 위하여 현우는 한 번에 두 개의 역기를 들어 옮기지는 않는다. 이때, 역기를 들어 옮기는 방법은 다음과 같이 세가지가 있다.

• 고정대위에 놓인 역기를 체력단련장의 바닥에 내려 놓는다.
• 고정대에 놓인 역기를 빈 고정대로 옮긴다.
• 체력단련장의 바닥에 놓인 역기를 빈 고정대로 옮긴다.

입력

출력

입출력 예

입력

4
6 7 5 11

출력

23

출처:acm