Rearrange Array

Given an array of n integers, the task is to rearrange the array so that all negative numbers appear before all non-negative numbers, while preserving the original relative order among the negatives and non-negatives.

For instance, if the input array is \([-1, 2, -3, 4, 5, -6]\), the correct rearranged output would be \([-1, -3, -6, 2, 4, 5]\). This problem tests your ability to manipulate and reorder arrays while keeping the stability of element order.

inputFormat

The input is read from standard input and has the following format:

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

outputFormat

Output the rearranged array as a single line of n space-separated integers to standard output.

6
-1 2 -3 4 5 -6

-1 -3 -6 2 4 5