Alya and Permutation
Contest: Codeforces Global Round 27
Difficulty rating: 1400
Tags: bitmasks, constructive algorithms, math

Alya has been given a hard problem. Unfortunately, she is too busy running for student council. Please solve this problem for her.

Given an integer $$$n$$$, construct a permutation $$$p$$$ of integers $$$1, 2, \ldots, n$$$ that maximizes the value of $$$k$$$ (which is initially $$$0$$$) after the following process.

Perform $$$n$$$ operations, on the $$$i$$$-th operation ($$$i=1, 2, \dots, n$$$),

- If $$$i$$$ is odd, $$$k=k\,\&\,p_i$$$, where $$$\&$$$ denotes the bitwise AND operation.
- If $$$i$$$ is even, $$$k=k\,|\,p_i$$$, where $$$|$$$ denotes the bitwise OR operation.

Input format:
The first line contains a single integer $$$t$$$ ($$$1\le t\le 500$$$) — the number of test cases.

The only line of each test case contains a single integer $$$n$$$ ($$$5\le n\le 2 \cdot 10^5$$$) — the length of the permutation.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output the maximum value of $$$k$$$ in the first line and output the permutation $$$p_1, p_2,\ldots, p_n$$$ in the second line.

If there are multiple such permutations, output any.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first test case, the value of $$$k$$$ is determined as follows:

$$$k = 0$$$ initially.

- On the $$$1$$$st operation, $$$1$$$ is odd, so Alya sets $$$k$$$ to be $$$k\&p_1 = 0\&2 = 0$$$.
- On the $$$2$$$nd operation, $$$2$$$ is even, so Alya sets $$$k$$$ to be $$$k|p_2 = 0|1 = 1$$$.
- On the $$$3$$$rd operation, $$$3$$$ is odd, so Alya sets $$$k$$$ to be $$$k\&p_3 = 1\&3 = 1$$$.
- On the $$$4$$$th operation, $$$4$$$ is even, so Alya sets $$$k$$$ to be $$$k|p_4 = 1|4 = 5$$$.
- On the $$$5$$$th operation, $$$5$$$ is odd, so Alya sets $$$k$$$ to be $$$k\&p_5 = 5\&5 = 5$$$.

The final value of $$$k$$$ is $$$5$$$. It can be shown that the final value of $$$k$$$ is at most $$$5$$$ for all permutations of length $$$5$$$. Another valid output is $$$[2, 3, 1, 4, 5]$$$.

For the second test case, the final value of $$$k$$$ is $$$7$$$. It can be shown that the final value of $$$k$$$ is at most $$$7$$$ for all permutations of length $$$6$$$. Other valid outputs include $$$[2, 4, 1, 6, 3, 5]$$$ and $$$[5, 2, 6, 1, 3, 4]$$$.

Example input:
6
5
6
7
8
9
10

Example output:
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

Editorial:
We can make $$$k$$$ what it needs to be using at most the last $$$5$$$ numbers of the permutation. Every other element can be assigned randomly.
We can split this up into several cases.
Case 1: $$$n$$$ is odd.
The last operation will be bitwise and. The bitwise and of $$$k$$$ with the last element which is less than or equal to $$$n$$$ is less than or equal to $$$n$$$. It is always possible to get the final $$$k$$$ value equal to $$$n$$$.
Let $$$l$$$ be the lowest bit of $$$n$$$. We can set the last $$$4$$$ numbers to be: $$$$$$l, l + (l == 1 ? 2 : 1), n - l, n$$$$$$
After the first $$$2$$$, $$$k$$$ will at least have the bit $$$l$$$. After the third one, $$$k$$$ will be equal to $$$n$$$. The bitwise and of $$$k$$$ and the last element equal to $$$n$$$ will be $$$n$$$.
Case 2: $$$n$$$ is even
Now the last operation will be a bitwise or so we can do better than $$$n$$$ here. The maximum possible $$$k$$$ will be the bitwise or of every number from $$$1$$$ to $$$n$$$.
Case 2a: $$$n$$$ is not a power of $$$2$$$.
Let $$$h$$$ be the highest bit of $$$n$$$. We can set the last $$$3$$$ numbers to: $$$$$$n, n - 1, h - 1$$$$$$
After the first $$$2$$$, $$$k$$$ will have at least the highest bit of $$$n$$$. After bitwise or-ing this with the third element, it will have all bits.
Case 2b: $$$n$$$ is a power of $$$2$$$.
We can set the last $$$5$$$ numbers to $$$$$$1, 3, n - 2, n - 1, n$$$$$$ After the first $$$2$$$, $$$k$$$ will have the $$$1$$$ bit turned on. After the fourth one, $$$k$$$ will have every bit except $$$n$$$ turned on or be equal to $$$n - 1$$$. The last element turns on the highest bit.