← 返回题目列表

Codeforces · 2035/C

C. Alya 和排列

中文机器翻译题面 查看原题

Alya 遇到了一个难题。不幸的是,她正忙于竞选学生会成员。请为她解决这个问题。

给定一个整数 $$$n$$$,构造一个整数 $$$1, 2, \ldots, n$$$ 的排列 $$$p$$$,在经过以下过程后最大化 $$$k$$$ 的值(最初为 $$$0$$$)。

对第 $$$i$$$ 操作执行 $$$n$$$ 操作 ($$$i=1, 2, \dots, n$$$),

- 如果 $$$i$$$ 为奇数,则 $$$k=k\,\&\,p_i$$$,其中 $$$\&$$$ 表示按位 AND 运算。
- 如果 $$$i$$$ 为偶数,则 $$$k=k\,|\,p_i$$$,其中 $$$|$$$ 表示按位 OR 运算。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 500$$$) — 测试用例的数量。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$5\le n\le 2 \cdot 10^5$$$) — 排列的长度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在第一行输出 $$$k$$$ 的最大值,在第二行输出排列 $$$p_1, p_2,\ldots, p_n$$$。

如果有多个这样的排列,则输出任意一个。

示例

输入 #1

6
5
6
7
8
9
10

输出 #1

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

注意

对于第一个测试用例,$$$k$$$ 的值确定如下:

$$$k = 0$$$ 最初。

- 在 $$$1$$$st 操作中,$$$1$$$ 是奇数,因此 Alya 将 $$$k$$$ 设置为 $$$k\&p_1 = 0\&2 = 0$$$。
- 在 $$$2$$$nd 操作中,$$$2$$$ 是偶数,因此 Alya 将 $$$k$$$ 设置为 $$$k|p_2 = 0|1 = 1$$$。
- 在 $$$3$$$rd 操作中,$$$3$$$ 是奇数,因此 Alya 将 $$$k$$$ 设置为 $$$k\&p_3 = 1\&3 = 1$$$。
- 在第 $$$4$$$ 次操作中,$$$4$$$ 是偶数,因此 Alya 将 $$$k$$$ 设置为 $$$k|p_4 = 1|4 = 5$$$。
- 在第 $$$5$$$ 操作中,$$$5$$$ 是奇数,因此 Alya 将 $$$k$$$ 设置为 $$$k\&p_5 = 5\&5 = 5$$$。

$$$k$$$ 的最终值为 $$$5$$$。可以证明,对于长度为 $$$5$$$ 的所有排列,$$$k$$$ 的最终值最多为 $$$5$$$。另一个有效输出是 $$$[2, 3, 1, 4, 5]$$$。

对于第二个测试用例,$$$k$$$ 的最终值为$$$7$$$。可以证明,对于长度为 $$$6$$$ 的所有排列,$$$k$$$ 的最终值最多为 $$$7$$$。其他有效输出包括 $$$[2, 4, 1, 6, 3, 5]$$$ 和 $$$[5, 2, 6, 1, 3, 4]$$$。