Spaceship

Interview

Time limit2sMemory limit512 MB

Summary

Reorder n enemy powers so that the last one equals the sum of all the others.

Level: Medium4 of 10
Topics: Math, Sorting, Greedy, Implementation
Solved: No attempts yet

Problem

Space Ranger is caught at an alien spaceship. He is surrounded by enemies. To break free he needs to destroy all enemies in some particular order.

There are n enemies around Space Ranger, the i-th of them has power fi. To break free Space Ranger needs to destroy all enemies in such order that the power of the last destroyed enemy is equal to the sum of powers of all other enemies.

Space Ranger is short of time, so he has failed to find the required order. Help him! Find the way to destroy all enemies and break free.

Input

The first line of input contains n, the number of enemies (2 ≤ n ≤ 105).

The second line contains n integers fi, the powers of the enemies (-109 ≤ fi ≤ 109).

Output

Output values fi in the order in which the enemies must be destroyed. If there are several ways to destroy all enemies and break free, print any one. It is guaranteed that there is at least one way to do it.

Examples2

Example 1
Input
```
3
2 5 3
```
Expected output
```
2 3 5
```
Example 2
Input
```
5
-1 1 0 1 -1
```
Expected output
```
-1 1 1 -1 0
```