← 返回题目列表

Codeforces · 1149/A

A. 前缀和素数

中文机器翻译题面 查看原题

我们正在赠送装有数字瓷砖的漂亮大袋子!我们想向您展示的袋子包含 $$$n$$$ 瓷砖。每个上面都写有一个数字 - $$$1$$$ 或 $$$2$$$。

但是,您必须满足一个条件才能获得奖品。您需要将袋子中的所有瓷砖按您希望的任何顺序按顺序放置。然后,我们将计算序列中所有前缀的总和,然后计算这些总和中有多少是素数。如果你想保住奖金,你需要最大限度地增加你获得的素数数量。

你能中奖吗?快点吧,袋子在等你!

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — 袋子中数字块的数量。以下行包含 $$$n$$$ 以空格分隔的整数 $$$a_1, a_2, \dots, a_n$$$ ($$$a_i \in \{1, 2\}$$$) — 写在图块上的值。

输出

输出输入序列 $$$(a_1, a_2, \dots, a_n)$$$ 的排列 $$$b_1, b_2, \dots, b_n$$$,最大化前缀和为素数的数量。如果存在多个最优排列,则输出任意一个。

示例

输入 #1

5
1 2 1 2 1

输出 #1

1 1 1 2 2

输入 #2

9
1 1 2 1 1 1 2 1 1

输出 #2

1 1 1 2 1 1 1 2 1

注意

第一个解决方案产生前缀和 $$$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}}$$$(五个素数)。素数标记为粗体和蓝色。在每种情况下,产生的素数数量都是最大可能的。