P8847 [JRKSJ R5] 1-1 A

This problem is an easier version of 1-1. The harder version is [1-1 B](https://www.luogu.com.cn/problem/P8848).

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.

The first line contains an integer $n$. The second line contains $n$ integers representing $a$.

Output one line with $n$ integers separated by spaces, representing the reordered sequence. If there are multiple solutions, output any one of them.

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. | $\text{Subtask}$ | $n \le$ | $\text{Score}$ | | :----------: | :----------: | :----------: | | $1$ | $10$ | $40$ | | $2$ | $10^6$ | $60$ | For $100\%$ of the testdata, $1 \le n \le 10^6$, and $a_i \in \{1,-1\}$. Translated by ChatGPT 5