Listalla on aluksi $n$ lukua. Joka vuorolla poistat listalta kaksi pienintä lukua ja lisäät listalle niiden summan. Jatkat näin, kunnes listalla on vain yksi luku.

Tulosta listalle lisättävät luvut siinä järjestyksessä kuin ne lisätään.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: listan koko alussa.

Seuraavalla rivillä on $n$ kokonaislukua $x_1,x_2,\dots,x_n$: listan sisältö.

Tuloste

Tulosta $n-1$ lukua tehtävänannon mukaisesti.

Rajat

• $2 \le n \le 2 \cdot 10^5$
• $1 \le x_i \le 10^9$

Esimerkki

Syöte:

4
2 3 1 2

Tuloste:

3 5 8

Selitys: Lista muuttuu näin: $[2,3,1,2] \rightarrow [2,3,3] \rightarrow [5,3] \rightarrow [8]$