Problem D
Tape Merge

Victoria has been given a large collection of ancient tapes to merge together into one large master tape. Each tape contains a number of records which are sorted according to their key values. Victoria knows from her data structures and algorithms course that the classical merging algorithm will take $n + m - 1$ key comparisons in the worst case to merge together two tapes that contain $n$ and $m$ records, respectively. She further knows that this number of comparisons is optimal if $|n - m| \le 1$. Your job is to tell Victoria how many key comparisons are required in the worst case if the number of key values on each tape is known in advance.

For example, suppose that there are 3 tapes $A$, $B$, and $C$ containing $2$, $3$, and $4$ records respectively. Merging $A$ and $B$ first and then the result together with $C$ requires $2+3-1 = 4$ comparisons for the first merge and $5+4-1 = 8$ on the second merge, for a total of $12$ key comparisons. If instead $B$ and $C$ are merged first, and then the result with $A$, the total is $14$. Thus the first method is better; in fact, it is optimum.

Input

The input consists of a series of up to $30$ test cases, followed by a line containing a $0$. Each test case consists of a line with an integer $k$ with $1 \le k \le 10\, 000$ followed by a line containing $k$ integers $n_1, n_2, \ldots , n_ k$ indicating the number of records on each tape. You may assume that $1 \le n_ i \le 50\, 000$ for $1 \le i \le k$.

Output

For each test case, on a single line, output the least number of comparisons required to merge all the input tapes into a single output tape.

3
2 3 4
5
1 2 3 4 5
0

12
29