Alternate Positive and Negative Numbers

You are given an array of (n) integers that contains both positive and negative numbers. Your task is to rearrange the array such that the positive and negative numbers appear in an alternating fashion. The rearrangement should start with a positive number and must maintain the original relative order of the positive numbers and the negative numbers.

For instance, given an array ([1, 2, 3, -4, -1, 4]), the correct rearrangement is ([1, -4, 2, -1, 3, 4]).

inputFormat

The first line contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers. These integers can be both positive and negative.

outputFormat

Output the rearranged array as a single line of space-separated integers, following the condition that positive and negative numbers alternate starting with a positive number.## sample

6
1 2 3 -4 -1 4

1 -4 2 -1 3 4