엘리어스 감마 코드

엘리어스 감마 코드(Elias gamma code)는 양의 정수로 이루어진 수열을 인코딩하는 데 쓰는 코드이다. 이 문제에서는 $0$도 인코딩할 수 있도록 변형한 코드를 사용한다.

정수 $n$을 인코딩하는 과정은 다음과 같다.

1. $n$을 이진수로 나타냈을 때의 비트 수를 $k$라고 한다. (단, $0$의 비트 수는 $1$로 본다.)
2. $0$을 $k-1$개 쓰고, 그 뒤에 $1$을 하나 쓴다. (이 부분을 prefix라고 부른다.)
3. 이어서 $n$을 이진수로 쓴다.

$0$부터 $8$까지 인코딩한 결과는 아래와 같다.

정수 수열을 인코딩하려면 수열의 각 수를 위 방법으로 코드로 바꾼 뒤, 수열에 나온 순서 그대로 이어 붙인다.

인코딩된 코드를 다시 원래 수로 디코딩할 때는, 이진수 표현 앞에 붙는 prefix가 핵심 역할을 한다. 인코딩된 수열을 읽을 때 $1$을 만나기 전에 $0$을 $k-1$개 읽었다면, 그 뒤의 $k$개 비트가 인코딩된 수라는 뜻이다.

인코딩 결과의 전체 길이를 줄이기 위해 다음 두 가지 최적화를 생각할 수 있다.

1. prefix는 원래 자신이 나타내는 비트 수 $k$가 정해져 있다. 그런데 수열에 비트 수가 정확히 $k$인 수가 하나도 없다면, 이 prefix를 $k+1$비트 수를 나타내는 데 사용할 수 있다. 만약 $k+1$비트를 나타내는 prefix가 이미 쓰이고 있다면 $k+2$비트를 나타내는 데 쓰고, 이런 식으로 계속 밀어 올린다. 이렇게 하면 그 수들의 prefix 길이가 짧아진다.
2. 비트 수가 $k$인 모든 수 앞에 $0$을 하나 붙이면, 그 수들은 모두 비트 수가 $k+1$이 된다. 이렇게 만든 뒤 최적화 1을 적용할 수도 있다. 이 방법은 비트 수가 $k$인 수는 매우 적고, 그보다 비트 수가 큰 수는 많은 경우에 효과적이다.

수열을 인코딩한 결과의 길이를 최소로 만들려고 한다. 수열의 구체적인 수는 주어지지 않고, 대신 비트 수가 $i$인 수의 개수를 $c_i$로 준다.

예를 들어 $c_1=2$, $c_2=4$, $c_3=0$, $c_4=1$인 경우를 생각하자. (수열 $2, 1, 3, 8, 0, 2, 3$이 이에 해당한다.) 최적화를 전혀 하지 않은 길이는 2×(1+1) + 4×(2+2) + 0×(3+3) + 1×(4+4) = 28이다. 최적화 1을 써서 prefix $001$을 $4$비트 수를 나타내는 데 쓰면 $1$비트를 줄일 수 있다. 또 최적화 2를 써서 $1$비트 수 앞에 $0$을 붙여 $2$비트로 만들 수 있다. 여기에 다시 최적화 1을 적용해 prefix $1$은 $2$비트 수에, prefix $01$은 $4$비트 수에 쓰면, 인코딩된 문자열의 길이는 6×(1+2) + 1×(2+4) = 24가 된다.

두 최적화는 여러 번 사용할 수 있다. 두 방법을 적절히 조합해 얻을 수 있는 최소 길이를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 정수 $n$이 주어진다. ($1 ≤ n ≤ 128$) 둘째 줄에는 $c_1$부터 $c_n$까지 $n$개의 값이 공백으로 구분되어 주어진다. ($0 ≤ c_i ≤ 10000$) 입력은 $n=0$인 줄로 끝나며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다, 주어진 수열을 인코딩했을 때 가능한 최소 엘리어스 감마 인코딩 길이를 한 줄에 하나씩 출력한다.