Mrs. Smith is trying to contact her husband, John Smith, but she forgot the secret phone number!
The 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.
The sequence of $$$n$$$ integers is called a permutation if it contains all integers from $$$1$$$ to $$$n$$$ exactly once.
The 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).
A subsequence $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$ where $$$1\leq i_1 < i_2 < \ldots < i_k\leq n$$$ is called increasing if $$$a_{i_1} < a_{i_2} < a_{i_3} < \ldots < a_{i_k}$$$. If $$$a_{i_1} > a_{i_2} > a_{i_3} > \ldots > 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.
For 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$$$.
Note, the lengths of LIS and LDS can be different.
So please help Mrs. Smith to find a permutation that gives a minimum sum of lengths of LIS and LDS.
The only line contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of permutation that you need to build.
Print a permutation that gives a minimum sum of lengths of LIS and LDS.
If there are multiple answers, print any.
4
3 4 1 2
2
2 1
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.
In 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.
Name |
---|