CF2035C.Alya and Permutation

Alya 遇到了一个难题。不幸的是，她正忙于竞选学生会。请你帮她解决这个问题。

给定一个整数 $n$，请构造一个 $1, 2, \ldots, n$ 的排列 $p$，使得在以下过程中最终得到的 $k$ 的值最大（初始时 $k=0$）。

进行 $n$ 次操作，在第 $i$ 次操作（$i=1,2,\ldots,n$）中：

• 如果 $i$ 是奇数，则 $k = k\,\&\,p_i$，其中 $\&$ 表示按位与运算。
• 如果 $i$ 是偶数，则 $k = k\,|\,p_i$，其中 $|$ 表示按位或运算。

第一行包含一个整数 $t$（$1\le t\le 500$），表示测试用例的数量。

每个测试用例仅一行，包含一个整数 $n$（$5\le n\le 2 \times 10^5$），表示排列的长度。

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

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

如果有多种排列方案，输出任意一种均可。

对于第一个测试用例，$k$ 的变化如下：

初始 $k=0$。

• 第 $1$ 次操作，$1$ 是奇数，所以 $k = k\&p_1 = 0\&2 = 0$。
• 第 $2$ 次操作，$2$ 是偶数，所以 $k = k|p_2 = 0|1 = 1$。
• 第 $3$ 次操作，$3$ 是奇数，所以 $k = k\&p_3 = 1\&3 = 1$。
• 第 $4$ 次操作，$4$ 是偶数，所以 $k = k|p_4 = 1|4 = 5$。
• 第 $5$ 次操作，$5$ 是奇数，所以 $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]$。

由 ChatGPT 4.1 翻译