Rearrange List with Negative Integers First

You are given a list of integers. Your task is to rearrange the list in such a way that all negative integers appear before all non-negative integers. The order of appearance among the negative integers and also among the non-negative integers must remain unchanged. This is known as a stable partition.

In mathematical terms, given an input list \( a = [a_1, a_2, \dots, a_n] \), you are to produce a list \( b = [b_1, b_2, \dots, b_n] \) such that:

[ \begin{cases} b_i < 0 & \text{for } 1 \leq i \leq k, \ b_i \ge 0 & \text{for } k+1 \leq i \leq n, \end{cases} ]

and the relative ordering of the negative and non-negative numbers is preserved as in the original list.

Note: The rearrangement should be done in place.

inputFormat

The input is taken from stdin in the following format:

n
x1 x2 x3 ... xn

Here, n is the number of integers in the list, and x1, x2, ..., xn are the space-separated integers.

outputFormat

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

## sample

5
1 -2 3 -4 5

-2 -4 1 3 5