A - Árbol de Fito

Languages: C, C++, Java, Python, Tiger, Haskell, JavaScript, Pascal, C#
Time & Memory limits: (details)

Un árbol es una estructura de datos ampliamente utilizada en la computación para modelar datos. Los arboles están formados por nodos que se conectan entre si utilizando aristas . En un árbol puede seleccionarse un nodo e identificarlo como el nodo raíz . A partir de este nodo se define una relación de parentesco de cada nodo con sus vecinos donde la raíz es padre de los nodos a los que esta conectado y estos a su vez son padre de sus vecinos (sin incluir a su padre). Un árbol binario cumple que todos sus nodos tienen a lo sumo 2 hijos, y se establece un orden entre ellos de forma tal que se les identifica como subárbol izquierdo y subárbol derecho.

Nuestro amigo Fito tomo un árbol binario y asignó ciertos valores a sus hojas, al terminar se dio cuenta de que estaba equilibrado . Esto significa que para todo nodo que no es hoja, la suma de los valores de las hojas de su subárbol izquierdo es igual a la suma de los valores de las hojas de su subárbol derecho.

Como de costumbre Fito se puso a jugar con el árbol y ahora nosotros tenemos que arreglar su desastre. Fito tomó en orden de izquierda a derecha los valores de las hojas del árbol anterior y los puso en una lista. Luego insertó en esta lista otros valores tratando de esconder su descubrimiento, tanto que ahora ni él mismo puede encontrarlo y está pidiendo nuestra ayuda.

Desgraciadamente nosotros no podemos recuperar su árbol, pero para que esté contento vamos a decirle, a partir de la lista que tiene, cuál pudo haber sido el árbol con mayor cantidad de hojas que él construyó.

Input

La entrada consiste en múltiples casos. Cada caso comienza con una línea que contiene un entero $n$ $(1 \le n \le 1000)$ que representa el tamaño de la lista. Luego en una línea habrá n enteros $a_i$ $(1\le a_i \le 500)$ separados por espacio con los valores de la misma. La entrada termina con un 0 y no habrá más de 50 casos.


Output

Para cada caso se debe imprimir en una línea la mayor cantidad de hojas que pudo haber tenido el árbol de Fito.

Sample test(s)

Input
9 3 4 1 3 1 2 4 4 6 4 3 12 6 3 10 10 9 8 7 6 5 4 3 2 1 11 10 9 8 7 6 5 4 3 2 1 1 8 1 1 1 1 1 1 1 1 0
Output
6 2 1 5 8