思路:

题目内容

2333拿到了一个$n$-排列,即$[1,n]$ 中每个整数恰好出现一次的序列。他想问问要如何摆放这些排列使得前缀和序列的相邻$gcd$ 之和最大？

这样说或许有些抽象。假设我们有一个排列:

$P = \{p_1 , p_2 , p_3 , ... , p_n\}$

那么其前缀和数组为:

$s = \{p_1 , p_1+p_2 , p_1+p_2+p_3 , ... , p_1+p_2+...+p_n\}$

相邻$gcd$数组为:

$G = \{s_1,gcd(s_1,s_2),gcd(s_2,s_3) , ... , gcd(s_{n-1} , s_{n})\}$

现在我们需要确定$p_1,p_2,...,p_n$ 的值，使得如下式子的结果最大化

输入描述

第一行一个整数$n(1 \leq n \leq 1e5)$

输出描述

输出一行$n$个整数，代表你构造的结果

数据范围说明

样例1

输入

5

输出

5 1 2 4 3

样例说明

若最优解的具体方案不唯一，输出任意一个即可。这里再给出一个可能方案:

$P_2 = [4, 2, 3, 1, 5]$