Tras el festival
En Indonesia (en la isla de Java, para ser más exactos) se ha celebrado un macrofestival de música en un gran recinto. Ahora que los asistentes duermen sus resacas en el hotel o en el avión, ha llegado el momento de que el recolector de basura deje todo acondicionado y limpio, tal y como estaba antes de empezar.
Afortunadamente, el público ha sido cuidadoso y ha dejado todos sus residuos dentro de los cubos correspondientes. Para recogerlos, los organizadores cuentan con un camión que es capaz de procesar dos cubos simultáneamente, levantando cada uno de ellos desde un lateral del camión y volcándolo en el interior, donde se realiza un primer procesado.
Para que el camión no se desequilibre y se produzca algún percance, es preferible que el peso de cada cubo de la pareja que se recoge cada vez sea lo más parecido posible. Sabiendo los pesos de todos los cubos, tenemos que decidir cómo emparejarlos.
Entrada
Cada caso de prueba comienza con un número indicando cuántos cubos hay que recoger. Siempre hay un número par de cubos, y nunca habrá más de 200.000.
A continuación, en otra línea, aparecen los pesos de cada uno de los cubos, separados por espacio. Ningún peso es mayor que 1.000.000.
La entrada termina con un 0, que no debe procesarse.
Salida
Por cada caso de prueba el programa escribirá la diferencia de pesos existente entre los cubos más diferentes en el mejor emparejamiento posible, es decir aquél que minimiza esa diferencia.
Entrada de ejemplo
4 43 40 41 42 6 22 22 20 25 26 27 0
Salida de ejemplo
1 3