版权声明

本题版权归 所有。

题目来源：https://www.luogu.com.cn/problem/P10038

题目描述

以下是某量子密码锁的说明书：

在密码锁中，有一条长度为 $n$（不能更改，$n$ 的具体取值见密码锁铭牌）的链，链上共有 $n$ 个结点。每个结点上可以存放至多一个原子。初始时，$1,2,\ldots,n$ 号原子以某个顺序（可以由用户自行调整）被存放在其中，每个结点存放一个原子。

定义 $i$ 号原子的电荷量为 $i!=1 \times 2\times 3 \times \ldots \times i$。

现有一个计时器 $b$（单位为秒），其初值为 $0$。

密码锁被加热后，以下事件依次循环发生，直至达成终止条件：

1. 位于链两端的原子被移除（这不会使链变短），不再对后续事件产生影响；
2. 判定终止条件：
   • 若此时链中剩下不多于 $1$ 个原子（也可以是 $0$ 个），则达成终止条件，密码锁瘫痪（此时计时器 $b$ 的值不会增加 $1$）；
   • 否则，将计时器 $b$ 的值增加 $1$。
3. 给每个原子标定运动方向（标定的运动方向是临时的，只生效一次，在下一次标定前会被重置）：
   • 计算它左边所有原子的电荷量之和，设计算结果为 $x$；
   • 计算它右边所有原子的电荷量之和，设计算结果为 $y$；
   • 如果 $x<y$，则标定方向为「向左」；
   • 如果 $x>y$，则标定方向为「向右」；
   • 可以证明，$x \ne y$。
4. 所有原子按照所标定的运动方向，移动一条边的距离，来到相邻的结点。

现在已经从铭牌上读取到了 $n$ 的值，定义密码锁的瘫痪用时为它瘫痪时 $b$ 的值。请恰当排列密码锁中 $n$ 个原子的初始顺序，最大化密码锁的瘫痪用时。

输入格式

一行一个正整数 $n$。

输出格式

一行 $n$ 个正整数，一个 $1 \sim n$ 的排列，表示你给 krjt 规划的排列方案：从左到右（或者从右到左，可以证明它们的瘫痪用时相等）依次输出 $n$ 个原子的编号。

答案可能有多个，输出一个即可。

样例

1

1

2

1 2

3

2 1 3

4

4 2 3 1

5

5 4 1 2 3

6

2 4 5 1 6 3

样例解释

$6$ 个样例的瘫痪用时分别为 $0,0,0,1,1,2$ 秒。

实际上，枚举可知：当 $n \le 6$ 时，输出任何一个 $1 \sim n$ 的排列都能 AC。

下面对样例 $6$ 进行模拟。在链的描述中：

• $0$ 表示该结点为空；
• $i$ 表示该结点上存放着 $i$ 号原子；
• $(x,y)$ 为计算结果。

1. 初始的链为 $\color{blue}2-4-5-1-6-3$；
2. $b$ 初始为 $0$；
3. 位于两端的原子被移除，链变为 $\color{blue}0-4-5-1-6-0$；
4. $b$ 增加至 $1$；
5. 计算，$4$ 个原子（从左向右）的结果分别为 $\color{black}(\color{red}0\color{black},841),(\color{red}24\color{black},721),(\color{red}144\color{black},720),(145,\color{red}0\color{black})$；
6. 根据结果，左边 $3$ 个原子（$4,5,1$）向左运动，最右边的原子（$6$）向右运动，链变为 $\color{blue}4-5-1-0-0-6$；
7. 位于两端的原子被移除，链变为 $\color{blue}0-5-1-0-0-0$；
8. $b$ 增加至 $2$；
9. 计算，$2$ 个原子（从左向右）的结果分别为 $\color{black}(\color{red}0\color{black},1),(120,\color{red}0\color{black})$；
10. 根据结果，左边的原子（$5$）向左运动，右边的原子（$1$）向右运动，链变为 $\color{blue}5-0-0-1-0-0$；
11. 位于两端的原子被移除，链变为 $\color{blue}0-0-0-1-0-0$；
12. 此时链中只剩下 $1$ 个原子（$1$），反应结束，密码锁瘫痪。

综上，样例 $6$ 的瘫痪用时为 $2$ 秒。

下发文件

请在这里下载下发文件。

这是一份可视化工具。

数据范围

本题共有 $100$ 个测试点，分别有 $n=1,2,\ldots,100$，每个 $1$ 分。

对于 $100\%$ 的数据，$1 \le n \le 100$。