Karamell

Karamell, Caramel, Caramello ou Caramelo. Diferentes idiomas, mas você sabe do que eu estou falando. Alice e Bob são irmãos gêmeos e também adoram caramelos! Por isso, como presente de aniversário, pediram caramelos para todos convidados da festa que estão organizando. No dia da festa, Alice e Bob receberam seus presentes: N sacolas de caramelos. A i-ésima sacola continha ai caramelos.

Como os aniversariantes não querem abrir as sacolas imediatamente, decidiram distribuir os caramelos da seguinte maneira: as sacolas serão consideradas em ordem e, no i-ésimo passo, os ai caramelos da i-ésima sacola são dados à pessoa que tiver menos caramelos naquele momento. Em caso de empate, Alice recebe os caramelos (afinal, “primeiro as damas”).

Uma coisa que eles não gostaram é que, dependendo da ordem em que as sacolas são consideradas, a quantidade final de caramelos que cada um recebe pode ser diferente. Por exemplo, se as sacolas estivessem ordenadas com as quantidades descritas pela sequência [1, 2, 2, 3], Alice terminaria com 3 e Bob com 5 caramelos. Por outro lado, caso fossem consideradas na ordem [1, 2, 3, 2], ambos terminariam com 4.

Você esqueceu de comprar caramelos para os aniversariantes, mas resolveu dar um presente ainda mais interessante: um programa que determina uma maneira de ordenar as sacolas de forma que Alice e Bob recebam a mesma quantidade de caramelos, se possı́vel.

A primeira linha contém um único inteiro $N$ $(1 ≤ N ≤ 100)$, indicando o número de sacolas. A segunda linha contém $N$ inteiros $a_1 , . . . , a_N$ $(1 ≤ a_i ≤ 100)$, onde ai indica o número de caramelos na sacola $i.

A saı́da deve conter uma única linha. Caso seja impossı́vel achar uma ordem como pedido, imprima −1. Caso contrário, imprima N inteiros separados por espaço, indicando uma ordenação válida dos valores ai que garanta que os caramelos serão divididos igualmente entre os irmãos.