Rearrange Array: Negative First

You are given an array of integers. Your task is to rearrange the array so that all negative numbers appear before all non-negative numbers (including zero). The relative order of the negative numbers should remain the same as in the input, and the relative order of the non-negative numbers should also remain unchanged.

For instance, if the input array is [-1, 2, -3, 4, -5], then the output should be [-1, -3, -5, 2, 4].

Note: Zero (0) is considered as a non-negative number.

The problem requires you to use standard input (stdin) and output (stdout) for receiving input and printing the result.

inputFormat

The first line of input contains an integer n, which denotes the number of elements in the array. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output the rearranged array as space-separated integers in a single line.## sample

5
-1 2 -3 4 -5

-1 -3 -5 2 4