K. 最不上升也不下降序列
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

在创世的第七日，上帝开始创造序列世界。

"要有排列"

于是，排列诞生了—— 1 到 n 的每个整数恰好出现一次的序列。

"要有子序列"

于是，子序列诞生了——从序列中删除零个或多个元素，保持剩余元素顺序，得到的新序列。

"要有上升"

于是，最长上升子序列（LIS）诞生了——最长的严格递增的子序列。

"要有下降"

于是，最长下降子序列（LDS）诞生了——最长的严格递减的子序列。

上帝看着这一切，沉思片刻，说：

"要既不上升也不下降"

作为序列世界的造物主，你需要构造一个长度为 n 的排列，让 LIS 长度与 LDS 长度之和 最小 。

Input

输入一个整数 n（1 ≤ n ≤ 2000），表示排列的长度。

Output

输出一行 n 个整数，表示你构造的排列，其 LIS 长度与 LDS 长度之和最小。

如果有多种可能的排列，输出任意一种即可。

Examples
Input
1
Output
1
Input
3
Output
1 3 2
Input
7
Output
1 4 3 2 7 6 5