← 返回题目列表

Codeforces · 1017/C

C. 电话号码

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

史密斯夫人正在尝试联系她的丈夫约翰·史密斯,但她忘记了秘密电话号码!

史密斯夫人唯一记得的是 $$$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]$$$ 也是有效的。