Brazo de reyes
El roscón de reyes es un bollo típico de Navidad. Se realiza con una masa dulce, se adorna con fruta escarchada y suele rellenarse con nata, crema o trufa. Dentro se esconde una figurita de cerámica (la "sorpresa") para que se la encuentre algún comensal. Muchas veces se esconde también un haba. Según la tradición, quien la encuentre deberá pagar el roscón.
A Yoko Cino le gustan mucho, pero su forma toroidal le parece un engorro, tanto a la hora de abrirlos para rellenarlos con nata, como cuando se parten raciones para los comensales. Por eso en lugar de hacerlos con forma de rosca, los hace estirados, al estilo de otro tipo de dulce, los brazos de gitano. Debido a eso los llama "brazos de reyes".
Tras hornearlos, llega el momento de abrirlos, separando la base y la "tapa" para meter dentro tanto la sorpresa y el haba como el relleno. Yoko insiste en que la parte inferior y la parte superior deben pesar lo mismo, o no será un "brazo de reyes gourmet", de modo que pone mucho mimo en ese corte.
Entrada
Cada caso de prueba comienza con un número 1 ≤ N ≤ 200.000 que indica el número de "secciones" de un brazo de reyes. A continuación vienen, en otra línea, N números entre 1 y 109. Se garantiza que la suma de todos esos números es mayor que N.
Cada número indica la altura de una sección del dulce. Su densidad es uniforme, de modo que si una determinada sección se corta por la mitad, ambas partes pesarán exactamente lo mismo.
La entrada termina con un 0, que no debe procesarse.
Salida
Por cada caso de prueba el programa escribirá un número entero con la altura a la que hay que hacer el corte del brazo de reyes para que el peso de ambas partes sea igual. Si resulta imposible, se dará el valor entero que haga que la diferencia sea mínima, con la parte inferior mayor.
Los cortes siempre son rectos de modo que todas las secciones se cortan a la misma altura. Yoko prefiere la precisión en el peso antes que la estética final del dulce, por lo que no le importa que la parte de arriba esté formada por varias piezas.
Entrada de ejemplo
4 2 2 2 2 1 3 6 10 10 2 10 10 2 0
Salida de ejemplo
1 2 5