Вам дано целое положительное число \(n\).
Найдите перестановку\(^\dagger\) \(p\) длины \(n\) такую, что не существует двух различных индексов \(i\) и \(j\) (\(1 \leq i, j < n\); \(i \neq j\)) таких, что \(p_i\) делит \(p_j\) и \(p_{i+1}\) делит \(p_{j+1}\).
Посмотрите примечание для примеров подходящих перестановок.
Можно доказать, что при ограничениях задачи существует по крайней мере одна подходящая перестановка \(p\).
\(^\dagger\) Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных выведите \(p_1, p_2, \ldots, p_n\).
Если существует несколько решений, вы можете вывести любое из них.
Примечание
В первом наборе входных данных \(p=[4,1,2,3]\) является допустимой перестановкой. Однако перестановка \(p=[1,2,3,4]\) не является допустимой перестановкой, так как мы можем выбрать \(i=1\) и \(j=3\). Тогда \(p_1=1\) делит \(p_3=3\), а \(p_2=2\) делит \(p_4=4\). Отметим, что и перестановка \(p=[3, 4, 2, 1]\) не является допустимой, так как при выборе \(i=3\) и \(j=2\) будет верно: \(p_3=2\) делит \(p_2=4\) и одновременно \(p_4=1\) делит \(p_3=2\).
Во втором наборе входных данных \(p=[1,2,3]\) является допустимой перестановкой. На самом деле все \(6\) перестановок длины \(3\) являются допустимыми.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
3
|
4 1 2 3
1 2 3
|