Rearrange Array: Negative Numbers First

You are given an array of integers. Your task is to rearrange the array so that all the negative numbers appear before all non-negative numbers. The relative order of the negative numbers should be preserved, as well as the relative order of the non-negative numbers.

More formally, let the original array be \(A = [a_1, a_2, \dots, a_n]\). You need to partition the array into two parts such that if \(a_i < 0\) and \(a_j \ge 0\), then the negative number \(a_i\) appears before the non-negative number \(a_j\). The order among negatives and among non-negatives must remain the same as in \(A\).

For example, given the array [3, -2, -1, 5, -6, 7, -8, 2], the output should be [-2, -1, -6, -8, 3, 5, 7, 2].

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains a single integer \(n\), denoting the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the array elements.

outputFormat

Print the rearranged array in a single line. The elements must be separated by a single space. All negative elements come first, followed by all non-negative elements, while preserving their original relative order.

## sample

8
3 -2 -1 5 -6 7 -8 2

-2 -1 -6 -8 3 5 7 2

</p>