Funny Permutation
Contest: Codeforces Round 826 (Div. 3)
Difficulty rating: 800
Tags: constructive algorithms, math

A sequence of $$$n$$$ numbers is called permutation if it contains all numbers from $$$1$$$ to $$$n$$$ exactly once. For example, the sequences $$$[3, 1, 4, 2]$$$, [$$$1$$$] and $$$[2,1]$$$ are permutations, but $$$[1,2,1]$$$, $$$[0,1]$$$ and $$$[1,3,4]$$$ are not.

For a given number $$$n$$$ you need to make a permutation $$$p$$$ such that two requirements are satisfied at the same time:

- For each element $$$p_i$$$, at least one of its neighbors has a value that differs from the value of $$$p_i$$$ by one. That is, for each element $$$p_i$$$ ($$$1 \le i \le n$$$), at least one of its neighboring elements (standing to the left or right of $$$p_i$$$) must be $$$p_i + 1$$$, or $$$p_i - 1$$$.
- the permutation must have no fixed points. That is, for every $$$i$$$ ($$$1 \le i \le n$$$), $$$p_i \neq i$$$ must be satisfied.

Let's call the permutation that satisfies these requirements funny.

For example, let $$$n = 4$$$. Then [$$$4, 3, 1, 2$$$] is a funny permutation, since:

- to the right of $$$p_1=4$$$ is $$$p_2=p_1-1=4-1=3$$$;
- to the left of $$$p_2=3$$$ is $$$p_1=p_2+1=3+1=4$$$;
- to the right of $$$p_3=1$$$ is $$$p_4=p_3+1=1+1=2$$$;
- to the left of $$$p_4=2$$$ is $$$p_3=p_4-1=2-1=1$$$.
- for all $$$i$$$ is $$$p_i \ne i$$$.

For a given positive integer $$$n$$$, output any funny permutation of length $$$n$$$, or output -1 if funny permutation of length $$$n$$$ does not exist.

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

The description of the test cases follows.

Each test case consists of f single line containing one integer $$$n$$$ ($$$2 \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, print on a separate line:

- any funny permutation $$$p$$$ of length $$$n$$$;
- or the number -1 if the permutation you are looking for does not exist.

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

Note:
The first test case is explained in the problem statement.

In the second test case, it is not possible to make the required permutation: permutations $$$[1, 2, 3]$$$, $$$[1, 3, 2]$$$, $$$[2, 1, 3]$$$, $$$[3, 2, 1]$$$ have fixed points, and in $$$[2, 3, 1]$$$ and $$$[3, 1, 2]$$$ the first condition is met not for all positions.

Example input:
5
4
3
7
5
2

Example output:
3 4 2 1
-1
6 7 4 5 3 2 1
5 4 1 2 3
2 1

Editorial:
We cannot make a funny permutation only when $$$n = 3$$$, because one of the neighboring elements of $$$3$$$ must be equal to $$$2$$$. Any permutation made in this way will not satisfy the conditions:
• The permutation [$$$3, 2, 1$$$] will have a fixed point $$$p_2 = 2$$$.
• The permutation [$$$1, 3, 2$$$] will have a fixed point $$$p_1 = 1$$$.
• The permutation [$$$2, 3, 1$$$] will not have a neighbor equal to $$$p_3 + 1 = 1 + 1 = 2$$$ for $$$p_3 = 1$$$.
For the remaining values of $$$n$$$, make the following observations:
• For $$$n = 2$$$, the only funny permutation is [$$$2, 1$$$].
• When $$$n \ge 4$$$, permutations of the form [$$$3, \dots, n, 2, 1$$$] will always be funny because all elements $$$p_i$$$ will have a neighbor equal to $$$p_i - 1$$$ or $$$p_i + 1$$$, and the permutation will have no fixed points ($$$p_{n-1} = 2$$$, $$$p_n = 1$$$, and for $$$3 \le i \le n - 2$$$ will always be true $$$p_i = i + 2$$$).