1719 測資加強 已 rejudge
1398 . 霍夫快編碼
TopCoder
Tags
Description
是的...從前從前，有個人叫做霍夫...
自從他學了神秘的編碼學以後，他開始不誤正業了(誤)！
他把所有他看到的東西通通編了碼...
是的！你的任務就是要改變霍夫快編碼的壞習慣，要搶先一步，在他把測資通通編碼之前先把它解決掉！
給你一篇文章中n種字元出現的次數，現在採用「三進位編碼」，也就是這n種字元每一種可以被編為包含0,1,2的序列。
相同地，每一個字元編碼後，都不可以是其他編碼後字元的前綴字串(prefix)，例如 012 與 01210 是不合法的編碼方式。
請問將這篇文章以最佳方式編碼後的文章長度為何？
Input Format
輸入可能包含多筆測試資料，以EOF作結束。
每筆測試資料的第一列有一個正整數n(1≦n≦100,000)，代表文章中有幾種字元。
接下來有n個正整數，分別代表每一種字元於文章中出現的次數，這些數字都不會超過 1,000,000。
Output Format
對於每一筆測試資料請輸出一列，包含一個數字：以最佳方式編碼後的文章長度。
Sample Input 1
4
10 15 20 100
5
1 2 3 4 5
10 15 20 100
5
1 2 3 4 5
Sample Output 1
170
21
21
Hints
Problem Source
原TIOJ1398 / 快樂暑假營第四次練習比賽。Problem Setter：Tmt。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 25 |
| 2 | 1 | 25 |
| 3 | 2 | 25 |
| 4 | 3 | 25 |