A11884. The Phone Number
编程题
普及/提高-
知识点
题目描述
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.
If there are multiple answers, print any.
输出格式
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.
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.
输入输出样例
输入 #1
4
输出 #1
3 4 1 2
输入 #2
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.
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.