史密斯夫人正在尝试联系她的丈夫约翰·史密斯,但她忘记了秘密电话号码!
史密斯夫人唯一记得的是 $$$n$$$ 的任何排列都可以是秘密电话号码。只有那些使秘密价值最小化的排列才可能是她丈夫的电话。
如果 $$$n$$$ 整数序列包含从 $$$1$$$ 到 $$$n$$$ 的所有整数恰好一次,则该序列称为排列。
电话号码的秘密值定义为最长递增子序列(LIS)的长度和最长递减子序列(LDS)的长度之和。
子序列 $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ 其中 $$$1\leq i_1 < i_2 < \ldots < i_k\leq n$$$ 如果 $$$a_{i_1} < a_{i_2} < a_{i_3} < \ldots < 则称为递增子序列a_{i_k}$$$。如果 $$$a_{i_1} > a_{i_2} > a_{i_3} > \ldots > a_{i_k}$$$,则子序列称为递减。如果一个增/减子序列在所有增/减子序列中具有最大长度,则该增/减子序列被称为最长。
例如,如果有一个排列$$$[6, 4, 1, 7, 2, 3, 5]$$$,则该排列的LIS将为$$$[1, 2, 3, 5]$$$,因此LIS的长度等于$$$4$$$。 LDS 可以是 $$$[6, 4, 1]$$$、$$$[6, 4, 2]$$$ 或 $$$[6, 4, 3]$$$,因此 LDS 的长度为 $$$3$$$。
注意,LIS 和 LDS 的长度可以不同。
所以请帮助史密斯夫人找到一种排列,给出 LIS 和 LDS 的长度之和最小。
输入
唯一一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 您需要构建的排列的长度。
输出
打印给出 LIS 和 LDS 长度最小和的排列。
如果有多个答案,请打印其中一个。
示例
输入 #1
4
输出 #1
3 4 1 2
输入 #2
2
输出 #2
2 1
注意
在第一个示例中,您可以构建排列 $$$[3, 4, 1, 2]$$$。 LIS 为 $$$[3, 4]$$$(或 $$$[1, 2]$$$),因此 LIS 的长度等于 $$$2$$$。 LDS 只能是 $$$[3, 1]$$$、$$$[4, 2]$$$、$$$[3, 2]$$$ 或 $$$[4, 1]$$$ 中的一个。 LDS 的长度也等于$$$2$$$。总和等于 $$$4$$$。请注意,$$$[3, 4, 1, 2]$$$ 并不是唯一有效的排列。
在第二个示例中,您可以构建排列 $$$[2, 1]$$$。 LIS 为 $$$[1]$$$(或 $$$[2]$$$),因此 LIS 的长度等于 $$$1$$$。 LDS 为 $$$[2, 1]$$$,因此 LDS 的长度等于 $$$2$$$。总和等于 $$$3$$$。请注意,排列 $$$[1, 2]$$$ 也是有效的。