题目描述
给定一个正整数 $n$。你需要找到，在所有使得 $\text{gcd}(1\times p_1,2\times p_2,\cdots,n \times p_n)$ 的值尽可能大的 $1\sim n$ 的排列 $p$ 中，字典序最小的排列 $p$。
其中：
- $1 \sim n$ 的排列表示长度为 $n$ 且 $1\sim n$ 均恰好出现一次的序列；
- $\text{gcd}(x_1,x_2,\cdots,x_n)$ 表示 $x_1,x_2,\cdots,x_n$ 的最大公因数；
- 对于两个 $1\sim n$ 的排列 $a,b$，$a$ 的字典序比 $b$ 小，当且仅当存在一个正整数 $i$，满足 $a$ 的前 $i-1$ 项与 $b$ 的前 $i-1$ 项均相同且 $a_i \lt b_i$。
输入格式
输入一行，包含一个正整数 $n$（$2\leq n \leq 10^5$）。
输出格式
输出一行，包含 $n$ 个正整数，表示满足条件的 $1\sim n$ 的排列 $p$。
样例
样例输入 1
2
样例输出 1
2 1
样例输入 2
3
样例输出 2
1 2 3
样例解释
对于第一组样例：
- 当 $p=\{1,2\}$ 时，$\text{gcd}(1\times1,2\times2)=1$；
- 当 $p=\{2,1\}$ 时，$\text{gcd}(1\times2,2\times1)=2$；
所以 $\{2,1\}$ 为满足条件的排列 $p$。
对于第二组样例：
- 当 $p=\{1,2,3\}$ 时，$\text{gcd}(1\times1,2\times2,3\times3)=1$；
- 当 $p=\{1,3,2\}$ 时，$\text{gcd}(1\times1,2\times3,3\times2)=1$；
- 当 $p=\{2,1,3\}$ 时，$\text{gcd}(1\times2,2\times1,3\times3)=1$；
- 当 $p=\{2,3,1\}$ 时，$\text{gcd}(1\times2,2\times3,3\times1)=1$；
- 当 $p=\{3,1,2\}$ 时，$\text{gcd}(1\times3,2\times1,3\times2)=1$；
- 当 $p=\{3,2,1\}$ 时，$\text{gcd}(1\times3,2\times2,3\times1)=1$；
所以 $\{1,2,3\}$ 为满足条件的排列 $p$。