Rearrange List: Negative Before Non-negative

Given a list of integers, rearrange it so that all negative numbers appear before the non-negative numbers (including zero) while preserving the relative order among the negative numbers and non-negative numbers.

Input Format: The first line contains an integer n representing the number of elements in the list. The second line contains n space-separated integers.

Output Format: Print the rearranged list as space-separated integers.

Note: If the list is empty, simply output nothing.

The rearrangement can be represented mathematically as follows:

\(arr = [a_1, a_2, \dots, a_n]\)

Let \(P = \{a_i | a_i < 0\}\) and \(Q = \{a_i | a_i \ge 0\}\), preserving the relative order in P and Q respectively, then the output is P concat Q.

inputFormat

The input is given from stdin and consists of two lines:

1. The first line contains a single integer n, the number of elements in the list.
2. The second line contains n space-separated integers.

outputFormat

Output the rearranged list to stdout as a single line of space-separated integers.

## sample

7
-1 2 -3 4 0 -5 6

-1 -3 -5 2 4 0 6