우편 묶음의 작업 기록

문제

어느 우체국에서는 운송함에 넣을 우편물을 여러 묶음으로 나누어 보관한다. 각 묶음의 크기는 그 안에 들어 있는 우편물의 개수다. 담당자는 운송함 하나에 넣을 최종 묶음을 만들기 위해 두 묶음을 합치는 작업을 반복한다. 두 묶음을 합치면 원래 두 묶음은 보관 목록에서 사라지고, 두 크기의 합을 크기로 갖는 새 묶음 하나가 목록에 들어간다. 이 우체국의 작업 규정은 다음과 같다. 현재 보관 목록에 있는 묶음 중 크기가 가장 작은 두 묶음을 반드시 골라 합친다. 크기가 같은 묶음이 여러 개라면 그중 어느 묶음을 골라도 된다. 같은 크기의 묶음도 서로 다른 묶음이므로 각각 하나씩 센다. 합쳐서 만든 새 묶음도 다음 작업부터 다른 묶음과 똑같이 선택 대상이 된다. 처음 입력된 묶음끼리만 합칠 수 있는 것은 아니다. 두 묶음을 합칠 때에는 새 묶음에 들어 있는 모든 우편물에 작업 확인 도장을 찍는다. 따라서 크기가 x와 y인 두 묶음을 합치는 작업에서 찍는 도장의 수는 x+y다. 같은 우편물이 여러 번 합쳐지는 묶음에 속하면 작업마다 도장을 다시 찍으며, 그 횟수를 모두 작업 기록에 더한다. 도장 수는 다음 작업에서 묶음을 고르는 기준에 영향을 주지 않는다. 담당자는 목록에 묶음이 정확히 하나 남으면 작업을 끝낸다. 처음부터 묶음이 하나라면 합치는 작업을 하지 않으므로 기록할 도장 수는 0이다. 입력에 주어진 순서는 보관 목록을 적은 순서일 뿐이며, 작업 중 그 순서를 유지할 필요는 없다. 처음 보관된 각 묶음의 크기가 주어질 때, 위 규정대로 모든 작업을 마칠 때까지 찍는 도장 수의 합을 구하는 프로그램을 작성한다.

입력

첫째 줄에 처음 묶음의 수 N이 주어진다. 둘째 줄에 각 묶음의 크기 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 모든 입력값은 정수이며 1≤N≤60,000, 1≤A_i≤9다.

출력

모든 작업에서 찍는 도장 수의 합을 정수 하나로 출력한다. 합치는 작업이 없으면 0을 출력한다.

4
2 2 3 7

25

1
9

0

5
1 1 1 1 1

12

출처: Devin.KR 자체 제작