Rearrange Array with Negative Numbers First

Given an array of integers, rearrange it so that all negative numbers appear before all non-negative numbers while maintaining the relative order of the negative numbers and the non-negative numbers. In other words, perform a stable partition where the negative numbers come first and the order within the negatives, as well as within the non-negatives, remains unchanged.

Note: Zero is considered as non-negative.

Example: For an input array of [-1, 2, -3, 4, -5], the output should be [-1, -3, -5, 2, 4].

inputFormat

The first line of input contains an integer n representing the number of elements in the array.

The second line contains n space-separated integers representing the array elements.

If n = 0, the array is empty.

outputFormat

Output the rearranged array as a sequence of integers separated by spaces in a single line. The rearranged array should have all negative numbers (if any) at the beginning in their original order, followed by all non-negative numbers in their original order.

5
-1 2 -3 4 -5

-1 -3 -5 2 4