Rearrange Array Elements by Sign
Given an array with an equal number of positive and negative integers, rearrange it so signs alternate, preserving relative order.
Input format
The first line contains N (even). The second line contains N nonzero integers — exactly N/2 positive and N/2 negative.
Output format
Print the array rearranged so signs alternate starting with a positive number, preserving the relative order within positives and within negatives.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
4
3 1 -2 -5Expected output
3 -2 1 -5Example 2
Input
2
-1 2Expected output
2 -1