LogiQuest

58. Negatives Before Positives

EasyArrayPartition

Print all negative numbers first and then all non-negative numbers, each group keeping its original order.

Input format

Line 1: n Line 2: n integers

Output format

The rearranged array.

Example 1

Input

6
3 -1 4 -5 0 -2

Output

-1 -5 -2 3 4 0

Example 2

Input

3
1 2 3

Output

1 2 3

Constraints

1 ≤ n ≤ 10⁵

Read input from standard input and print the answer to standard output. Your code is judged against 5 test cases, most of them hidden.

Loading the MyLoginn IDE…