Custom Sorting of Sequences

You are given a sequence of integers. Your task is to rearrange the sequence by following these rules:

• All negative integers must appear before any positive integers.
• The relative order among the negative integers, as well as that among the positive integers, must be preserved as in the original sequence.
• All zeros in the sequence should be moved to the end, preserving their original relative order.

For example, if the input is 4 -3 0 2 -7 0 1 -6, the output should be -3 -7 -6 4 2 1 0 0.

inputFormat

The first line contains a single integer n indicating the number of elements in the sequence.

The second line contains n integers separated by spaces representing the sequence.

outputFormat

Output a single line containing the rearranged sequence of integers. The numbers should be separated by a single space.

8
4 -3 0 2 -7 0 1 -6

-3 -7 -6 4 2 1 0 0