#XMOJ12282. 星际快递
星际快递
说明
时间限制:1 Sec
内存限制:256 MB
输入文件:express.in 输出文件:express.out
小明在星际快递空间站实习。今天到港一批包裹,编号恰好是 $1$ 到 $n$ 各一个。站长要把它们排成一列,并制定了一个「壮观值」:
从这列包裹里从左往右挑出若干个(不一定相邻)编号——若挑出的编号一路严格增大,称为一段「上升梯队」,其长度取能挑出的最大值;若一路严格减小,称为一段「下降梯队」,长度同样取最大。壮观值就是「上升梯队最大长度」加上「下降梯队最大长度」。
现在要把这 $n$ 个包裹排成一列(每个编号恰好出现一次)。请帮小明求出:壮观值最小可能是多少?并给出一种达到最小值的摆放顺序。
输入格式
第一行一个整数 $T$,表示到港批次的组数。
每组数据一个整数 $n$,表示该批包裹的编号范围是 $1$ 到 $n$。
输出格式
输出 $T$ 组答案,每组两行:
- 第一行一个整数,表示最小的壮观值;
- 第二行 $n$ 个整数,表示一种达到最小值的摆放顺序($1$ 到 $n$ 的排列)。
答案不唯一——任意一种达到最小壮观值的摆放顺序都会被判正确。
样例
样例 1
1
7
6
3 2 1 6 5 4 7
样例说明:
这列摆放中,上升梯队最长可以挑出 个(如 ),下降梯队最长可以挑出 个(如 ),壮观值为 。
样例 2
1
4
4
2 1 4 3
样例说明:
这列摆放中,上升梯队最长 个,下降梯队最长 个,壮观值为 。
样例 3
1
10
7
4 3 2 1 8 7 6 5 10 9
样例说明:
这列摆放中,上升梯队最长 个,下降梯队最长 个,壮观值为 。
数据范围
$1 \le T \le 10$。
$1 \le n \le 10^5$。
对于 $50\%$ 的测试点,$n \le 8$;对于 $100\%$ 的测试点,$n \le 10^5$。
相关
在下列比赛中: