CF1149A Prefix Sum Primes

我们正在赠送装有数字牌的大礼包！你将获得一个包含 $n$ 张数字牌的礼包。每张牌上写着一个数字——要么是 $1$，要么是 $2$。 不过，你必须满足一个条件才能领取奖品。你需要将礼包中的所有牌按任意顺序排列成一个序列。然后，我们会计算该序列所有前缀的和，并统计这些前缀和中有多少个是质数。如果你想保留奖品，你需要让质数的数量尽可能多。 你能赢得奖品吗？快来挑战吧，大礼包等着你！

输入的第一行包含一个整数 $n$（$1 \leq n \leq 200\,000$），表示礼包中数字牌的数量。第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$（$a_i \in \{1, 2\}$），表示每张牌上的数字。

输出 $b_1, b_2, \dots, b_n$，为输入序列 $(a_1, a_2, \dots, a_n)$ 的一个排列，使得前缀和为质数的数量最大。如果有多种最优排列，输出任意一种即可。

第一个样例的前缀和为 $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}}$（共构造出五个质数）。质数用加粗蓝色标记。在每种情况下，构造出的质数数量都是最大可能的。 由 ChatGPT 4.1 翻译