268. Sort by Distance from Zero

Core1000 ms256 MBSolved by 0%

Sort n integers by how far they are from zero, smallest distance first.

Values at the same distance, such as -3 and 3, must keep the order they had in the input. That property is called STABILITY, and it is what this problem is really about.

-3 1 -2 -> 1 -2 -3

Some sorts preserve the original order of equal items and some do not. Java's Arrays.sort on objects and Python's sort are stable; C's qsort makes no promise at all. So the tie rule has to be written into the comparison rather than assumed, or the same code gives different answers in different languages.

Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`

Input

The first line contains an integer n. The second line contains n integers.

Output

Print the values ordered by absolute value, ties keeping their input order, separated by single spaces.

Input3 -3 1 -2

Output1 -2 -3

Noteorders by distance rather than by value

Input2 -1 1

Output-1 1

Noteis a tie, so the input order must be preserved

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution