Rearrange Negatives and Positives In Place

Given an array of integers, rearrange its elements so that all negative numbers come before all positive numbers. The relative order within the negatives or positives does not matter. The reordering must be performed in place without using extra space.

Note: If the array is empty, output nothing.

inputFormat

The input consists of two lines. The first line contains an integer n representing the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Output the rearranged array as space-separated integers on a single line. All negative integers should appear before any non-negative integers. The order within each partition does not matter.

6
1 -2 3 -4 -5 6

-5 -2 -4 3 1 6