CF1149A.Prefix Sum Primes

We're giving away nice huge bags containing number tiles! A bag we want to present to you contains $n$ tiles. Each of them has a single number written on it — either $1$ or $2$.

However, there is one condition you must fulfill in order to receive the prize. You will need to put all the tiles from the bag in a sequence, in any order you wish. We will then compute the sums of all prefixes in the sequence, and then count how many of these sums are prime numbers. If you want to keep the prize, you will need to maximize the number of primes you get.

Can you win the prize? Hurry up, the bags are waiting!

我们正在赠送装有数字方块的精美超大袋子！送给你的一袋中包含 $n$ 个方块，每个方块上都写有一个数字——非 $1$ 即 $2$。

不过，要想获得这份奖品，你必须满足一个条件：你需要将袋中所有方块按任意顺序排成一个序列。接着，我们将计算该序列所有前缀的和，并统计其中有多少个和是质数。若想成功赢得奖品，你需要使这个质数的个数尽可能多。

你能赢得这份奖品吗？快行动吧，袋子已经在等你了！

The first line of the input contains a single integer $n$ ($1 \leq n \leq 200\,000$) — the number of number tiles in the bag. The following line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$ ($a_i \in {1, 2}$) — the values written on the tiles.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 200\,000$），表示袋中数字方块的数量。接下来一行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$（其中每个 $a_i \in \{1, 2\}$），表示各方块上所写的数值。

Output a permutation $b_1, b_2, \dots, b_n$ of the input sequence $(a_1, a_2, \dots, a_n)$ maximizing the number of the prefix sums being prime numbers. If there are multiple optimal permutations, output any.

输出输入序列 $(a_1, a_2, \dots, a_n)$ 的一个排列 $b_1, b_2, \dots, b_n$，使得其前缀和中为质数的个数最多。若存在多个最优排列，输出任意一个即可。

The first solution produces the prefix sums $1, \mathbf{\color{blue}{2}}, \mathbf{\color{blue}{3}}, \mathbf{\color{blue}{5}}, \mathbf{\color{blue}{7}}$ (four primes constructed), while the prefix sums in the second solution are $1, \mathbf{\color{blue}{2}}, \mathbf{\color{blue}{3}}, \mathbf{\color{blue}{5}}, 6, \mathbf{\color{blue}{7}}, 8, 10, \mathbf{\color{blue}{11}}$ (five primes). Primes are marked bold and blue. In each of these cases, the number of produced primes is maximum possible.

第一种解法生成的前缀和为 $1, \mathbf{\color{blue}{2}}, \mathbf{\color{blue}{3}}, \mathbf{\color{blue}{5}}, \mathbf{\color{blue}{7}}$（共构造出四个质数），而第二种解法的前缀和为 $1, \mathbf{\color{blue}{2}}, \mathbf{\color{blue}{3}}, \mathbf{\color{blue}{5}}, 6, \mathbf{\color{blue}{7}}, 8, 10, \mathbf{\color{blue}{11}}$（共五个质数）。质数以粗体蓝色标出。在上述两种情况下，所生成的质数个数均为可能的最大值。