← 返回题目列表

Codeforces · 49/C

C. 处置

中文机器翻译题面 查看原题

瓦夏购买了贝尔兰著名诗人彼佳的n册文集。卷数从 1 到 n。他认为单纯按照他们的顺序来排列这本书是不行的。 Vasya 希望最小化处置除数的数量 - 正整数 i,使得至少有一个 j (1 ≤ j ≤ n) 为真:j mod i = 0,同时 p(j) mod i = 0,其中 p(j) 是位于第 j 位的书的编号,mod 是取除法余数的运算。当然,一卷可以恰好占据一处,一处也可以恰好站立一卷。

Help Vasya — 找到除数最少的卷配置。

输入

第一行包含数字 n (1 ≤ n ≤ 100000),表示卷数和可用空间的数量。

输出

打印 n 个数字 — 所寻求的除数最小的配置。第 j 个数字 (1 ≤ j ≤ n) 应等于 p(j) — 第 j 个位置上的书的编号。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

2

输出 #1

2 1

输入 #2

3

输出 #2

1 3 2