Generate Permutation
Contest: Codeforces Round 967 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms

There is an integer sequence $$$a$$$ of length $$$n$$$, where each element is initially $$$-1$$$.

Misuki has two typewriters where the first one writes letters from left to right, with a pointer initially pointing to $$$1$$$, and another writes letters from right to left with a pointer initially pointing to $$$n$$$.

Misuki would choose one of the typewriters and use it to perform the following operations until $$$a$$$ becomes a permutation of $$$[1, 2, \ldots, n]$$$

- write number: write the minimum positive integer that isn't present in the array $$$a$$$ to the element $$$a_i$$$, $$$i$$$ is the position where the pointer points at. Such operation can be performed only when $$$a_i = -1$$$.
- carriage return: return the pointer to its initial position (i.e. $$$1$$$ for the first typewriter, $$$n$$$ for the second)
- move pointer: move the pointer to the next position, let $$$i$$$ be the position the pointer points at before this operation, if Misuki is using the first typewriter, $$$i := i + 1$$$ would happen, and $$$i := i - 1$$$ otherwise. Such operation can be performed only if after the operation, $$$1 \le i \le n$$$ holds.

Your task is to construct any permutation $$$p$$$ of length $$$n$$$, such that the minimum number of carriage return operations needed to make $$$a = p$$$ is the same no matter which typewriter Misuki is using.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \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 a line of $$$n$$$ integers, representing the permutation $$$p$$$ of length $$$n$$$ such that the minimum number of carriage return operations needed to make $$$a = p$$$ is the same no matter which typewriter Misuki is using, or $$$-1$$$ if it is impossible to do so.

If there are multiple valid permutations, you can output any of them.

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

Note:
In the first testcase, it's possible to make $$$a = p = [1]$$$ using $$$0$$$ carriage return operations.

In the second testcase, it is possible to make $$$a = p = [1, 2]$$$ with the minimal number of carriage returns as follows:

If Misuki is using the first typewriter:

- Write number: write $$$1$$$ to $$$a_1$$$, $$$a$$$ becomes $$$[1, -1]$$$
- Move pointer: move the pointer to the next position. (i.e. $$$2$$$)
- Write number: write $$$2$$$ to $$$a_2$$$, $$$a$$$ becomes $$$[1, 2]$$$

If Misuki is using the second typewriter:

- Move pointer: move the pointer to the next position. (i.e. $$$1$$$)
- Write number: write $$$1$$$ to $$$a_1$$$, $$$a$$$ becomes $$$[1, -1]$$$
- Carriage return: return the pointer to $$$2$$$.
- Write number: write $$$2$$$ to $$$a_2$$$, $$$a$$$ becomes $$$[1, 2]$$$

It can be proven that the minimum number of carriage returns needed to transform $$$a$$$ into $$$p$$$ when using the first typewriter is $$$0$$$ and it is $$$1$$$ when using the second one, so this permutation is not valid.

Similarly, $$$p = [2, 1]$$$ is also not valid, so there is no solution for $$$n = 2$$$.

In the third testcase, it is possibile to make $$$a = p = [3, 1, 2]$$$ with $$$1$$$ carriage return with both the first and the second typewriter. It can be proven that, for both typewriters, it is impossible to write $$$p$$$ with $$$0$$$ carriage returns.

With the first typewriter it is possible to:

- Move pointer: move the pointer to the next position. (i.e. $$$2$$$)
- Write number: write $$$1$$$ to $$$a_2$$$, $$$a$$$ becomes $$$[-1, 1, -1]$$$
- Move pointer: move the pointer to the next position. (i.e. $$$3$$$)
- Write number: write $$$2$$$ to $$$a_3$$$, $$$a$$$ becomes $$$[-1, 1, 2]$$$
- Carriage return: return the pointer to $$$1$$$.
- Write number: write $$$3$$$ to $$$a_1$$$, $$$a$$$ becomes $$$[3,1,2]$$$

With the second typewriter it is possible to:

- Move pointer: move the pointer to the next position. (i.e. $$$2$$$)
- Write number: write $$$1$$$ to $$$a_2$$$, $$$a$$$ becomes $$$[-1, 1, -1]$$$
- Carriage return: return the pointer to $$$3$$$.
- Write number: write $$$2$$$ to $$$a_3$$$, $$$a$$$ becomes $$$[-1, 1, 2]$$$
- Move pointer: move the pointer to the next position. (i.e. $$$2$$$)
- Move pointer: move the pointer to the next position. (i.e. $$$1$$$)
- Write number: write $$$3$$$ to $$$a_1$$$, $$$a$$$ becomes $$$[3, 1, 2]$$$

Example input:
3
1
2
3

Example output:
1
-1
3 1 2

Editorial:
Consider the cost function:
Let $$$c_{cw}, c_{ccw}$$$ denote the minimum number of operations needed to produce $$$p_n$$$ if the roulette is rotating clockwise/counter-clockwise. Let's consider how to calculate them.
For $$$c_{cw}$$$, obviously we need to do the operation at least once, and we need to do one extra operation whenever the position of value $$$x + 1$$$ is before $$$x$$$, for all $$$x \in [1, n - 1]$$$, so $$$c_{cw} = 1 + (\text{#}x \in [1, n - 1] \text{ such that } \mathrm{pos}_x > \mathrm{pos}_{x + 1})$$$.
Similarly, $$$c_{ccw} = 1 + (\text{#}x \in [1, n - 1] \text{ such that } \mathrm{pos}_x < \mathrm{pos}_{x + 1})$$$.
Since for $$$x \in [1, n - 1]$$$, either $$$\mathrm{pos}_x < \mathrm{pos}_{x + 1}$$$ or $$$\mathrm{pos}_x > \mathrm{pos}_{x + 1}$$$ would be true, $$$c_{cw} + c_{ccw} = n + 1$$$, which is a constant, so $$$c_{cw} = c_{ccw} \leftrightarrow c_{cw} = \frac{n + 1}{2}$$$, which only has solution when $$$n$$$ is odd, and such $$$p_n$$$ can be constructed easily (for example, $$$\{N - 1, N, N - 3, N - 2, ..., 4, 5, 2, 3, 1\}$$$).