Alternate Positive and Negative Arrangement

You are given an array of integers. Your task is to rearrange the array so that positive and negative numbers appear alternatively. If there are extra elements of one type (either positive or negative), they should be appended at the end in their original relative order.

Formally, given an array A of size n, rearrange it such that elements at even indices (0-indexed) are positive and elements at odd indices are negative, whenever possible. If a complete alternation is not possible because one type runs out, simply append the remaining elements in the same order as they appeared in A.

The expected time complexity is \(O(n)\) and the extra space complexity should be \(O(1)\) aside from the input array.

inputFormat

The first line contains an integer n, the number of elements in the array.

The second line contains n space-separated integers representing the array elements.

outputFormat

Output the rearranged array as a sequence of space-separated integers in a single line.

## sample

5
2 -1 -3 4 5

2 -1 4 -3 5

</p>