A. Простые префиксные суммы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мы раздаем огромные красивые мешки, содержащие плитки с числами!

Мешок, который мы хотим вам подарить, содержит $$$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)$$$, максимизирующую количество префиксных сумм, которые являются простыми числами.

Если есть несколько оптимальных перестановок, вы можете вывести любую.

Примеры
Входные данные
5
1 2 1 2 1
Выходные данные
1 1 1 2 2
Входные данные
9
1 1 2 1 1 1 2 1 1
Выходные данные
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}}$$$ (пять простых).

Простые числа отмечены жирно и синим цветом. В каждом из этих случаев количество полученных простых является максимально возможным.