Reorder List: Negative First

Given a list of integers, reorder the list such that all negative integers appear before all non-negative integers while preserving the relative order of the negative integers and the non-negative integers separately.

Formally, let (A) be the input list. Partition it into two sub-lists: (N = {a \in A : a < 0}) and (P = {a \in A : a \ge 0}). The result should be the list (N \Vert P), where (\Vert) denotes concatenation, with the elements in (N) and (P) retaining their original order from (A).

For example, if (A = [3, -1, 2, -4, -6, 5, -3, 2]) then the output is ([-1, -4, -6, -3, 3, 2, 5, 2]).

inputFormat

The first line contains an integer (n), the number of elements. The second line contains (n) space-separated integers.

outputFormat

Output the reordered list with elements separated by a space. There should be a trailing newline at the end.## sample

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

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