Background

This problem is an easier version of 1-1. The harder version is 1-1 B.

Problem Description

You are given a sequence $a$. For all $i \in [1,n]$, $a_i \in \{1,-1\}$.

You may reorder the sequence arbitrarily. You need to minimize the maximum subarray sum of the sequence after reordering.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers representing $a$.

Output Format

Output one line with $n$ integers separated by spaces, representing the reordered sequence.

If there are multiple solutions, output any one of them.

4
1 1 -1 -1

1 -1 -1 1

Hint

Definition of the maximum subarray sum: the maximum value of the sum over any subarray of the sequence, i.e. $\max_{1\le l\le r\le n} \sum_{i=l}^r a_i$.

This problem uses $\text{Special Judge}$. As long as your output satisfies the requirements, it will be accepted.

The input and output files of this problem are large, so please use appropriate input and output methods.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le n \le 10^6$, and $a_i \in \{1,-1\}$.

Translated by ChatGPT 5