Gorroneando helado
Heladio, Laura y Domingo son tres devoradores de helados. Les gustan todos los sabores, desde clásicos como vainilla o chocolate, hasta cosas esotéricas como nubes o palomitas de maíz, sin olvidarse de sabores "de nicho" como turrón o ron con pasas.
Hoy están asistiendo a una celebración donde hay Viennetta, esas barras de helado de nata con láminas de chocolate para cortar en raciones. Los anfitriones han puesto a disposición de los asistentes la barra más grande del mercado y la han enriquecido con fresas y frutos rojos, creando una combinación difícil de olvidar.
Heladio, Laura y Domingo tienen la intención secreta de comerse la gigante barra de Viennetta entre los tres pero, dado que los frutos rojos les gustan todavía más que el propio helado, han llegado a un acuerdo. Partirán, cuando nadie mire, la barra de Viennetta en tres grandes raciones de modo que el número de frutos rojos que quede en cada una sea lo más parecido posible al de las demás. Eso significa que la resta entre el número de la ración más poblada y el de la menos poblada debe ser lo menor posible.
Entrada
Cada caso de prueba comienza con un número 3 ≤ n ≤ 200.000 con el número de porciones de la barra de helado. A continuación aparecen n números entre 1 y 10.000 con la cantidad de frutos rojos en cada una.
Salida
Por cada caso de prueba el programa decidirá cuántas porciones debe comerse cada amigo para que los tres coman el número de frutos rojos lo más parecido posible. La barra de Viennetta se partirá en tres grandes raciones, por lo que las porciones que cada uno comerá serán consecutivas en la entrada.
Se escribirá, para cada caso, la diferencia entre el número de frutos rojos que come la persona a la que más le corresponden y la que menos come con el corte más equitativo posible del helado. Lo importante no es el número de porciones que toma cada uno (que podría ser muy distinto), sino el de frutos rojos.
Entrada de ejemplo
3 1 1 1 4 1 1 2 1 6 1 2 3 1 2 3 6 3 1 1 1 1 2
Salida de ejemplo
0 1 2 0