Мы раздаем огромные красивые мешки, содержащие плитки с числами!
Мешок, который мы хотим вам подарить, содержит \(n\) плиток. На каждой из них записано одно число — \(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}}\) (пять простых).
Простые числа отмечены жирно и синим цветом. В каждом из этих случаев количество полученных простых является максимально возможным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 1 2 1
|
1 1 1 2 2
|
|
2
|
9
1 1 2 1 1 1 2 1 1
|
1 1 1 2 1 1 1 2 1
|