Вам дано целое положительное число \(n\).
Весом перестановки \(p_1, p_2, \ldots, p_n\) называется количество индексов \(1\le i\le n\) таких, что индекс \(i\) делит значение \(p_i\). Найдите перестановку \(p_1,p_2,\dots, p_n\) с минимальным возможным весом (среди всех перестановок длины \(n\)).
Перестановкой называется массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, а \([1,2,2]\) не является (\(2\) встречается дважды), и \([1,3,4]\) тоже не является перестановкой (\(n=3\), но в массиве есть \(4\)).
Выходные данные
Для каждого набора входных данных выведите строку, содержащую \(n\) целых чисел \(p_1, p_2,\dots, p_n\); перестановка \(p\) должна иметь минимальный возможный вес.
Если существуют несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных единственная подходящая перестановка \(p=[1]\). Ее вес равен \(1\).
Во втором наборе один из возможных ответов это перестановка \(p=[2,1,4,3]\). Можно показать, что \(1\) делит \(p_1\), но ни один индекс \(i\) не делит \(p_i\) для \(i=2,3,4\), поэтому вес этой перестановки \(1\). Не существует перестановки длины \(4\) с меньшим весом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1
4
|
1
2 1 4 3
|