Minimizing Maximum Subsegment Sum

You are given a sequence \(a\) of length \(n\) where every element \(a_i\) is either \(1\) or \(-1\). You are allowed to rearrange (i.e. permute) the sequence arbitrarily. Your task is to output a rearranged sequence such that the maximum subsegment (i.e. contiguous subarray) sum is minimized.

It can be shown that if the number of \(1\)'s is \(p\) and the number of \(-1\)'s is \(q\), then the minimum attainable maximum subsegment sum is

[ \max{1,, p-q} ]

Note that the maximum subsegment sum is defined as the maximum sum over all nonempty contiguous subarrays. In particular, if \(p=0\) (i.e. there are no \(1\)'s) then the answer is \(-1\) because every subsegment has a negative sum.

If there are multiple valid answers, any one will be accepted.

inputFormat

The input consists of two lines. The first line contains one integer \(n\) \((1 \le n \le 10^5)\) representing the length of the sequence. The second line contains \(n\) space-separated integers, each being either \(1\) or \(-1\).

outputFormat

Output one line containing \(n\) space‐separated integers (each \(1\) or \(-1\)) representing a rearrangement of the original sequence such that the maximum subsegment sum is minimized.

sample

3
1 -1 1

1 -1 1