Rearrange Array with Negatives at the Front

You are given an array of integers. Your task is to rearrange the array such that all negative numbers appear before all non-negative numbers while preserving their relative order.

Formally, if the input array is \(a = [a_1, a_2, \dots, a_n]\), you are required to construct an array \(b\) where:

[ b = [\text{all } a_i \text{ such that } a_i < 0, \text{ in the same order they appear in } a,; \text{followed by all } a_j \text{ such that } a_j \ge 0, \text{ in the same order as in } a]. ]

If the array is empty, simply output an empty array.

inputFormat

The input is given via standard input and consists of two lines:

• The first line contains an integer \(N\) denoting 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 in a single line. The elements should be printed in order and separated by a single space.

4
-3 -1 -2 -4

-3 -1 -2 -4