The Elias gamma code is a simple code which can be used to encode a sequence of positive integers. We will use a modified code which is also able to encode zeros. To encode an integer n, do the following: 1. Letkbethenumberofbitsofn 2. Write k − 1 zeros followed by a 1 3. Write n in binary Examples Number Binary 0 0 1 1 2 10 3 11 4 100 5 101 6 110 7 111 8 1000 Number of bits Prefix Code 1 1 10 1 1 11 2 01 0110 2 01 0111 3 001 001100 3 001 001101 3 001 001110 3 001 001111 4 0001 00011000 A sequence of integers is encoded by writing the codes of the individual integers of the sequence in the same order as the integers appear in the sequence. The prefix of k additional bits before the binary representation of each integer is needed to be able to decode the encoded integers. So when reading the encoding of a sequence of integers, if we read k − 1 zeros followed by a one, it means that there are k bits following which are the binary representation of the next encoded integer. If we want to shorten the length of the encoding of a sequence of integers, there may be still some room for improvement; we will consider the following two optimizations:
2/2 optimization 1 and use prefix 1 for the integers with 2 bits, prefix ‘01’ for the integer with 4 bits, and we get the new length of 6 × (1 + 2) + 1 × (2 + 4) = 24. Both optimizations can possibly be used several times. Note that for the second optimization, it is not easy to decide when and how to use it. The goal is to combine these two optimizations in the best possible way, that means we want to find an encoding of a given sequence of integers that has minimum length among all encodings using elias gamma coding with any combination of these two optimizations. Input The input file contains several test cases. Each test case starts with a line containing an integer n, (1 ≤ n ≤ 128). The next line contains the values c1, ..., cn (0 ≤ ci ≤ 10000). Input is terminated by n = 0. Output For each test case print one line with the minimum length of an encoding of the given input sequence. Note: The first sample test case corresponds to the example given in the problem description. Sample Input 4 2401 5 94243 11 44 56 96 26 73 80 77 50 33 16 78 0 Sample Output 24 99 5494