{"raw_statement":[{"iden":"statement","content":"Mrs. Smith is trying to contact her husband, John Smith, but she forgot the secret phone number!\n\nThe only thing Mrs. Smith remembered was that any permutation of $n$ can be a secret phone number. Only those permutations that minimize secret value might be the phone of her husband.\n\nThe sequence of $n$ integers is called a permutation if it contains all integers from $1$ to $n$ exactly once.\n\nThe secret value of a phone number is defined as the sum of the length of the longest increasing subsequence (_LIS_) and length of the longest decreasing subsequence (_LDS_).\n\nA subsequence $a_{i_1}, a_{i_2}, \\ldots, a_{i_k}$ where $1\\leq i_1 &lt; i_2 &lt; \\ldots &lt; i_k\\leq n$ is called increasing if $a_{i_1} &lt; a_{i_2} &lt; a_{i_3} &lt; \\ldots &lt; a_{i_k}$. If $a_{i_1} &gt; a_{i_2} &gt; a_{i_3} &gt; \\ldots &gt; a_{i_k}$, a subsequence is called decreasing. An increasing/decreasing subsequence is called longest if it has maximum length among all increasing/decreasing subsequences.\n\nFor example, if there is a permutation $[6, 4, 1, 7, 2, 3, 5]$, _LIS_ of this permutation will be $[1, 2, 3, 5]$, so the length of _LIS_ is equal to $4$. _LDS_ can be $[6, 4, 1]$, $[6, 4, 2]$, or $[6, 4, 3]$, so the length of _LDS_ is $3$.\n\nNote, the lengths of _LIS_ and _LDS_ can be different.\n\nSo please help Mrs. Smith to find a permutation that gives a minimum sum of lengths of _LIS_ and _LDS_."},{"iden":"input","content":"The only line contains one integer $n$ ($1 \\le n \\le 10^5$) — the length of permutation that you need to build."},{"iden":"output","content":"Print a permutation that gives a minimum sum of lengths of _LIS_ and _LDS_.\n\nIf there are multiple answers, print any."},{"iden":"examples","content":"Input\n\n4\n\nOutput\n\n3 4 1 2\n\nInput\n\n2\n\nOutput\n\n2 1"},{"iden":"note","content":"In the first sample, you can build a permutation $[3, 4, 1, 2]$. _LIS_ is $[3, 4]$ (or $[1, 2]$), so the length of _LIS_ is equal to $2$. _LDS_ can be ony of $[3, 1]$, $[4, 2]$, $[3, 2]$, or $[4, 1]$. The length of _LDS_ is also equal to $2$. The sum is equal to $4$. Note that $[3, 4, 1, 2]$ is **not** the only permutation that is valid.\n\nIn the second sample, you can build a permutation $[2, 1]$. _LIS_ is $[1]$ (or $[2]$), so the length of _LIS_ is equal to $1$. _LDS_ is $[2, 1]$, so the length of _LDS_ is equal to $2$. The sum is equal to $3$. Note that permutation $[1, 2]$ is also valid."}],"translated_statement":[{"iden":"statement","content":"史密斯夫人试图联系她的丈夫约翰·史密斯，但她忘记了秘密电话号码！\n\n史密斯夫人唯一记得的是，任意一个长度为 $n$ 的排列都可能是秘密电话号码。只有那些使秘密值最小的排列才可能是她丈夫的电话号码。\n\n一个包含从 $1$ 到 $n$ 所有整数恰好各一次的 $n$ 个整数序列被称为排列。\n\n电话号码的秘密值定义为最长递增子序列（_LIS_）的长度与最长递减子序列（_LDS_）的长度之和。\n\n子序列 $a_(i_1), a_(i_2), dots.h, a_(i_k)$，其中 $1 lt.eq i_1 < i_2 < dots.h < i_k lt.eq n$，若满足 $a_(i_1) < a_(i_2) < a_(i_3) < dots.h < a_(i_k)$，则称为递增子序列；若满足 $a_(i_1) > a_(i_2) > a_(i_3) > dots.h > a_(i_k)$，则称为递减子序列。若一个递增/递减子序列的长度在所有此类子序列中最大，则称为最长递增/递减子序列。\n\n例如，对于排列 $[ 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$。\n\n请注意，_LIS_ 和 _LDS_ 的长度可以不同。\n\n请帮助史密斯夫人找到一个排列，使得 _LIS_ 和 _LDS_ 的长度之和最小。\n\n输入仅包含一个整数 $n$（$1 lt.eq n lt.eq 10^5$）——你需要构造的排列的长度。\n\n请输出一个使 _LIS_ 和 _LDS_ 长度之和最小的排列。\n\n如果有多个答案，输出任意一个即可。\n\n在第一个样例中，你可以构造排列 $[ 3, 4, 1, 2 ]$。_LIS_ 是 $[ 3, 4 ]$（或 $[ 1, 2 ]$），因此 _LIS_ 的长度为 $2$。_LDS_ 可以是 $[ 3, 1 ]$、$[ 4, 2 ]$、$[ 3, 2 ]$ 或 $[ 4, 1 ]$ 之一，其长度也为 $2$。总和为 $4$。请注意，$[ 3, 4, 1, 2 ]$ 并不是唯一的有效排列。\n\n在第二个样例中，你可以构造排列 $[ 2, 1 ]$。_LIS_ 是 $[ 1 ]$（或 $[ 2 ]$），因此 _LIS_ 的长度为 $1$。_LDS_ 是 $[ 2, 1 ]$，因此 _LDS_ 的长度为 $2$。总和为 $3$。请注意，排列 $[ 1, 2 ]$ 也是有效的。"},{"iden":"input","content":"输入仅包含一个整数 $n$（$1 lt.eq n lt.eq 10^5$）——你需要构造的排列的长度。"},{"iden":"output","content":"请输出一个使 _LIS_ 和 _LDS_ 长度之和最小的排列。如果有多个答案，输出任意一个即可。"},{"iden":"examples","content":"输入\n4\n输出\n3 4 1 2\n\n输入\n2\n输出\n2 1"},{"iden":"note","content":"在第一个样例中，你可以构造排列 $[ 3, 4, 1, 2 ]$。_LIS_ 是 $[ 3, 4 ]$（或 $[ 1, 2 ]$），因此 _LIS_ 的长度为 $2$。_LDS_ 可以是 $[ 3, 1 ]$、$[ 4, 2 ]$、$[ 3, 2 ]$ 或 $[ 4, 1 ]$ 之一，其长度也为 $2$。总和为 $4$。请注意，$[ 3, 4, 1, 2 ]$ 并不是唯一的有效排列。\n\n在第二个样例中，你可以构造排列 $[ 2, 1 ]$。_LIS_ 是 $[ 1 ]$（或 $[ 2 ]$），因此 _LIS_ 的长度为 $1$。_LDS_ 是 $[ 2, 1 ]$，因此 _LDS_ 的长度为 $2$。总和为 $3$。请注意，排列 $[ 1, 2 ]$ 也是有效的。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the permutation.  \nLet $ \\pi = (\\pi_1, \\pi_2, \\dots, \\pi_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $.  \nLet $ \\mathrm{LIS}(\\pi) $ denote the length of the longest increasing subsequence of $ \\pi $.  \nLet $ \\mathrm{LDS}(\\pi) $ denote the length of the longest decreasing subsequence of $ \\pi $.  \n\n**Objective**  \nFind a permutation $ \\pi $ of $ \\{1, 2, \\dots, n\\} $ that minimizes:  \n$$\n\\mathrm{LIS}(\\pi) + \\mathrm{LDS}(\\pi)\n$$\n\n**Constraint**  \n$ 1 \\leq n \\leq 10^5 $\n\n**Optimal Construction**  \nLet $ k = \\lceil \\sqrt{n} \\rceil $.  \nPartition the set $ \\{1, 2, \\dots, n\\} $ into $ k $ contiguous blocks, each of size at most $ k $, such that the $ i $-th block contains $ k $ consecutive integers (except possibly the last block).  \nArrange the permutation by concatenating the blocks in decreasing order of their elements, where within each block the elements are in increasing order.  \n\nThat is, define:  \n$$\n\\pi = \\left[ B_k^{\\uparrow}, B_{k-1}^{\\uparrow}, \\dots, B_1^{\\uparrow} \\right]\n$$  \nwhere $ B_j = \\{ (j-1)k + 1, (j-1)k + 2, \\dots, \\min(jk, n) \\} $, and $ B_j^{\\uparrow} $ denotes the elements of $ B_j $ in increasing order.\n\nThen:  \n$$\n\\mathrm{LIS}(\\pi) = k, \\quad \\mathrm{LDS}(\\pi) = k, \\quad \\text{so} \\quad \\mathrm{LIS}(\\pi) + \\mathrm{LDS}(\\pi) = 2k = 2\\lceil \\sqrt{n} \\rceil\n$$  \nThis achieves the theoretical minimum by the Erdős–Szekeres theorem.","simple_statement":null,"has_page_source":false}