Permutations & Primes
Contest: Codeforces Round 884 (Div. 1 + Div. 2)
Difficulty rating: 1000
Tags: constructive algorithms, math

You are given a positive integer $$$n$$$.

In this problem, the $$$\operatorname{MEX}$$$ of a collection of integers $$$c_1,c_2,\dots,c_k$$$ is defined as the smallest positive integer $$$x$$$ which does not occur in the collection $$$c$$$.

The primality of an array $$$a_1,\dots,a_n$$$ is defined as the number of pairs $$$(l,r)$$$ such that $$$1 \le l \le r \le n$$$ and $$$\operatorname{MEX}(a_l,\dots,a_r)$$$ is a prime number.

Find any permutation of $$$1,2,\dots,n$$$ with the maximum possible primality among all permutations of $$$1,2,\dots,n$$$.

Note:

- A prime number is a number greater than or equal to $$$2$$$ that is not divisible by any positive integer except $$$1$$$ and itself. For example, $$$2,5,13$$$ are prime numbers, but $$$1$$$ and $$$6$$$ are not prime numbers.
- A permutation of $$$1,2,\dots,n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

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

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 $$$n$$$ integers: a permutation of $$$1,2,\dots,n$$$ that achieves the maximum possible primality.

If there are multiple solutions, print any of them.

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

Note:
In the first test case, there are $$$3$$$ pairs $$$(l,r)$$$ with $$$1 \le l \le r \le 2$$$, out of which $$$2$$$ have a prime $$$\operatorname{MEX}(a_l,\dots,a_r)$$$:

- $$$(l,r) = (1,1)$$$: $$$\operatorname{MEX}(2) = 1$$$, which is not prime.
- $$$(l,r) = (1,2)$$$: $$$\operatorname{MEX}(2,1) = 3$$$, which is prime.
- $$$(l,r) = (2,2)$$$: $$$\operatorname{MEX}(1) = 2$$$, which is prime.

In the second test case, $$$\operatorname{MEX}(1) = 2$$$ is prime, so the primality is $$$1$$$.

In the third test case, the maximum possible primality is $$$8$$$.

Example input:
3
2
1
5

Example output:
2 1
1
5 2 1 4 3

Editorial:
The cases $$$n \le 2$$$ can be handled separately. For $$$n \ge 3$$$, any construction with $$$a_1 = 2, a_{\lfloor (n+1)/2 \rfloor} = 1, a_n = 3$$$ is optimal.
We can prove this as follows: Note that since $$$2$$$ and $$$3$$$ are both prime, any $$$(l,r)$$$ with $$$l \le \left\lfloor \frac{n+1}{2} \right\rfloor \le r$$$ has a prime $$$\operatorname{MEX}(a_l,\dots,a_r)$$$ except for possibly $$$(l,r) = (1,n)$$$, where $$$\operatorname{MEX}(a_1,\dots,a_n) = n+1$$$. Therefore the primality of this array is $$$\left\lfloor \frac{n+1}{2} \right\rfloor \cdot \left\lceil \frac{n+1}{2} \right\rceil - [n+1\text{ is not prime}]$$$, where $$$[P] = 1$$$ if proposition $$$P$$$ is true and $$$0$$$ if $$$P$$$ is false. On the other hand, for any permutation of $$$1,\dots,n$$$, let $$$k$$$ be the index with $$$a_k = 1$$$. The primality of this array cannot exceed $$$k(n+1-k)-[n+1\text{ is not prime}]$$$, since any pair $$$(l,r)$$$ with prime $$$\operatorname{MEX}(a_l,\dots,a_r) \ge 2$$$ must satisfy $$$l \le k \le r$$$, and additionally $$$\operatorname{MEX}(a_1,\dots,a_n) = n+1$$$ no matter what the permutation is. The function $$$f(k) = k(n+1-k)$$$ is a quadratic which is maximized at $$$k = \left\lfloor \frac{n+1}{2} \right\rfloor$$$, so $$$k(n+1-k)-[n+1\text{ is not prime}] \le \left\lfloor \frac{n+1}{2} \right\rfloor \cdot \left\lceil \frac{n+1}{2} \right\rceil - [n+1\text{ is not prime}]$$$ as required.
The time complexity is $$$\mathcal{O}(n)$$$ (note that we don't even need to sieve for primes!).