Lexicographically Smallest Maximum Order Permutation

A permutation is a bijection on the set \(\{1,2,\ldots,n\}\). The order of a permutation \(p\) is defined as the smallest positive integer \(k\) such that for every \(i=1,2,\ldots,n\) we have

\[ p(p(\cdots(p(i))\cdots)) = i \quad (\text{applied } k \text{ times}) \]

For example, for \(n=3\) the permutation defined by \(p(1)=3,\; p(2)=2,\; p(3)=1\) has order \(2\) because \[ p(p(1))=1,\; p(p(2))=2,\; p(p(3))=3. \]

Among all permutations of \(\{1,2,\ldots,n\}\) we wish to choose one having the maximum possible order. For instance, when \(n=5\) the maximum attainable order is \(6\). One permutation with order \(6\) is \[ p(1)=4,\; p(2)=5,\; p(3)=2,\; p(4)=1,\; p(5)=3. \]

However, among all permutations whose order is maximum, we require the lexicographically smallest one. More precisely, if we express a permutation in one‐line notation as \(p(1),p(2),\ldots,p(n)\), we say that \(p\) is lexicographically smaller than \(r\) if there exists an index \(i\) such that \(p(j)=r(j)\) for all \(j<i\) but \(p(i)<r(i)\). For \(n=5\) the lexicographically smallest permutation with maximum order is \[ p(1)=2,\; p(2)=1,\; p(3)=4,\; p(4)=5,\; p(5)=3. \]

Your task is to, given the integer \(n\) (with \(1 \le n \le 10\)), output the lexicographically smallest permutation (in one‐line notation) among those that have the maximum permutation order.

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 10\)) representing the number of elements.

outputFormat

Output the permutation as \(n\) space‐separated integers: \(p(1)\, p(2)\, \ldots\, p(n)\), where the permutation is the lexicographically smallest one among all permutations that achieve the maximum order.

sample

1

1