Reordering of Array Elements by Negativity

You are given an integer N and an array of N integers. Your task is to rearrange the elements of the array such that all negative numbers appear at the beginning and all non-negative (positive and zero) numbers appear at the end. Importantly, the relative order of the negative numbers should be preserved, as well as the relative order of the non-negative numbers.

This problem can be defined using the following mathematical description:

Let \( A = [a_1, a_2, \dots, a_N] \). Rearrange \( A \) into \( B = [b_1, b_2, \dots, b_N] \) where \[ B = \{ a_i : a_i < 0 \} \cup \{ a_i : a_i \ge 0 \} \] with the order among elements in each group unchanged.

Example:

Input: 8
       1 -2 3 -4 -1 4 -6 5
Output: -2 -4 -1 -6 1 3 4 5

inputFormat

The first line contains an integer N representing the number of elements in the array. The second line contains N space-separated integers which represent the array's elements.

Input Format:

N
a1 a2 ... aN

outputFormat

Output the rearranged array in a single line with the numbers separated by a single space. The output should contain exactly N integers.

Output Format:

b1 b2 ... bN

## sample

8
1 -2 3 -4 -1 4 -6 5

-2 -4 -1 -6 1 3 4 5