#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

样例说明:

这列摆放中,上升梯队最长可以挑出 33 个(如 1,4,71,4,7),下降梯队最长可以挑出 33 个(如 3,2,13,2,1),壮观值为 66。

样例 2

1
4
4
2 1 4 3

样例说明:

这列摆放中,上升梯队最长 22 个,下降梯队最长 22 个,壮观值为 44。

样例 3

1
10
7
4 3 2 1 8 7 6 5 10 9

样例说明:

这列摆放中,上升梯队最长 33 个,下降梯队最长 44 个,壮观值为 77。

数据范围

$1 \le T \le 10$。

$1 \le n \le 10^5$。

对于 $50\%$ 的测试点,$n \le 8$;对于 $100\%$ 的测试点,$n \le 10^5$。