Вам дано целое положительное число \(n\).
В этой задаче через \(\operatorname{MEX}\) для набора целых чисел \(c_1,c_2,\dots,c_k\) обозначим наименьшее положительное целое число \(x\), которое не встречается в наборе \(c\).
Простотой массива \(a_1,\dots,a_n\) назовём количество пар \((l,r)\), таких что \(1 \le l \le r \le n\) и \(\operatorname{MEX}(a_l,\dots,a_r)\) является простым числом.
Найдите произвольную перестановку чисел \(1,2,\dots,n\) с максимально возможным значением простоты среди всех перестановок \(1,2,\dots,n\).
Обратите внимание:
- Целое число, не меньшее \(2\), называется простым, если его целыми положительными делителями являются только \(1\) и оно само. Например, \(2,5,13\) — простые числа, а \(1\) и \(6\) не простые.
- Перестановкой чисел \(1,2,\dots,n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел, задающих перестановку \(1,2,\dots,n\), на которой достигается максимально возможная простота.
Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных есть всего \(3\) пары \((l,r)\) с \(1 \le l \le r \le 2\), из которых \(2\) имеют простое значение \(\operatorname{MEX}(a_l,\dots,a_r)\):
- \((l,r) = (1,1)\): \(\operatorname{MEX}(2) = 1\), что не является простым.
- \((l,r) = (1,2)\): \(\operatorname{MEX}(2,1) = 3\), что является простым.
- \((l,r) = (2,2)\): \(\operatorname{MEX}(1) = 2\), что является простым.
Отсюда, простота равна
\(2\).
Во втором наборе входных данных \(\operatorname{MEX}(1) = 2\) является простым, так что простота равна \(1\).
В третьем наборе входных данных максимально возможная простота равна \(8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
1
5
|
2 1
1
5 2 1 4 3
|