Elias Gamma Code

Time limit1sMemory limit128 MB

Summary

Given counts of numbers by binary bit length, choose prefix shifts and optional leading zeros to minimize the total encoded length.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

The Elias gamma code is a code used to encode a sequence of positive integers. In this problem we use a modified version that can also encode $0$ .

An integer $n$ is encoded as follows.

Let $k$ be the number of bits of $n$ written in binary. (The number of bits of $0$ is taken to be $1$ .)
Write $k-1$ zeros, followed by a single $1$ . (This part is called the prefix.)
Then write $n$ in binary.

The encodings of the numbers $0$ through $8$ are shown below.

Number	Binary	Bits	Prefix	Code
0	0	1	1	10
1	1	1	1	11
2	10	2	01	0110
3	11	2	01	0111
4	100	3	001	001100
5	101	3	001	001101
6	110	3	001	001110
7	111	3	001	001111
8	1000	4	0001	00011000

To encode a sequence of integers, convert each number to its code as above and concatenate the codes in the order the numbers appear in the sequence.

When decoding a code back to the original number, the prefix in front of the binary representation is essential. While reading the encoded sequence, if you read $k-1$ zeros before reading a $1$ , it means the next $k$ bits are the encoded number.

To shorten the total length of the encoding, consider the following two optimizations.

A prefix normally stands for a fixed bit count $k$ . If the sequence contains no number whose bit count is exactly $k$ , this prefix may instead be used to stand for numbers of $k+1$ bits. If a prefix already stands for $k+1$ bits, use it for $k+2$ bits, and so on, shifting up step by step. This shortens the prefix of those numbers.
If you prepend a $0$ to every number whose bit count is $k$ , all of them become numbers of $k+1$ bits; you can then apply optimization 1. This is effective when there are very few numbers with $k$ bits but many numbers with more than $k$ bits.

We want to minimize the total length of the encoded sequence. The actual numbers of the sequence are not given; instead, the count of numbers whose bit count is $i$ is given as $c_i$ .

For example, consider $c_1=2$ , $c_2=4$ , $c_3=0$ , $c_4=1$ . (The sequence $2, 1, 3, 8, 0, 2, 3$ is one such case.) Without any optimization the length is 2×(1+1) + 4×(2+2) + 0×(3+3) + 1×(4+4) = 28. Using optimization 1, the prefix $001$ can be used for $4$ -bit numbers, saving $1$ bit. Using optimization 2, prepend a $0$ to the $1$ -bit numbers to make them $2$ -bit numbers. Applying optimization 1 again, using prefix $1$ for $2$ -bit numbers and prefix $01$ for $4$ -bit numbers, the length of the encoded string becomes 6×(1+2) + 1×(2+4) = 24.

Both optimizations may be applied multiple times. Write a program that finds the minimum length obtainable by combining the two methods appropriately.

Input

The input consists of several test cases. The first line of each test case contains an integer $n$ ( $1 ≤ n ≤ 128$ ). The second line contains $n$ values $c_1$ through $c_n$ , separated by spaces ( $0 ≤ c_i ≤ 10000$ ). The input ends with a line containing $n=0$ , which should not be processed.

Output

For each test case, print on its own line the minimum possible Elias gamma encoding length for the given sequence.

Examples3

Example 1

Input

4
2 4 0 1
5
9 4 2 4 3
11
44 56 96 26 73 80 77 50 33 16 78
0

Expected output

24
99
5494

Example 2
Input
```
1
1
0
```
Expected output
```
2
```
Example 3
Input
```
1
0
0
```
Expected output
```
0
```