冬日狂想曲

1000MS 512MB

题目描述

"又到了这个季节了。"

窗外飘起了细雪，放学后的第二音乐室格外安静。为了准备即将到来的学园祭，一位钢琴手正在独自打磨她的独奏曲目。她认为，一首能够触动人心的曲子，不应该只有平铺直叙的音阶，而应当包含充满张力的跳跃。

钢琴的琴键被标记为 $1$ 到 $n$ 的整数。为了追求极致的技巧与情感表达，她决定编写一段特殊的"全音程练习曲"。这段旋律需要满足以下两个条件：

1. 全键覆盖：旋律由 $n$ 个音符组成，且 $1$ 到 $n$ 的每个琴键恰好被按下一遍（即序列是 $1$ 到 $n$ 的一个排列）。
2. 全音程跳跃：为了展现旋律的丰富性，每一次手指在琴键间移动的跨度（即相邻两个音符编号之差的绝对值）必须互不相同。

换句话说，如果旋律序列为 $A$，那么所有的"音程" ${ |A_1 - A_2|, |A_2 - A_3|, \dots, |A_{n-1} - A_n| }$ 中，任意两个数值都不能相等。

请你帮助她构造出这段完美的练习曲乐谱。

输入描述

一个整数 $n$ ($2 \le n \le 10^5$)，表示琴键的数量。

输出描述

输出一行 $n$ 个整数，表示琴键被按下的顺序。如果存在多种符合条件的乐谱，输出任意一种即可。

输入样例

6

输出样例

4 1 6 2 3 5

琴键按下的顺序为 $4 \to 1 \to 6 \to 2 \to 3 \to 5$。产生的音程跳跃分别为：

• $|4 - 1| = 3$
• $|1 - 6| = 5$
• $|6 - 2| = 4$
• $|2 - 3| = 1$
• $|3 - 5| = 2$

可以验证，上述 $5$ 个跳跃距离没有重复，符合要求。