[Solution] Funny Permutation solution codeforces

Table of Contents

Funny Permutation solution codeforces

Funny Permutation solution codeforces – A sequence of 𝑛n numbers is called permutation if it contains all numbers from 11 to 𝑛n exactly once. For example, the sequences [3,1,4,2][3,1,4,2], [11] and [2,1][2,1] are permutations, but [1,2,1][1,2,1][0,1][0,1] and [1,3,4][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 𝑝𝑖pi, at least one of its neighbors has a value that differs from the value of 𝑝𝑖pi by one. That is, for each element 𝑝𝑖pi (1𝑖𝑛1≤i≤n), at least one of its neighboring elements (standing to the left or right of 𝑝𝑖pi) must be 𝑝𝑖+1pi+1, or 𝑝𝑖1pi−1.
  • the permutation must have no fixed points. That is, for every 𝑖i (1𝑖𝑛1≤i≤n), 𝑝𝑖𝑖pi≠i must be satisfied.

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

[Solution] Funny Permutation solution codeforces

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

  • to the right of 𝑝1=4p1=4 is 𝑝2=𝑝11=41=3p2=p1−1=4−1=3;
  • to the left of 𝑝2=3p2=3 is 𝑝1=𝑝2+1=3+1=4p1=p2+1=3+1=4;
  • to the right of 𝑝3=1p3=1 is 𝑝4=𝑝3+1=1+1=2p4=p3+1=1+1=2;
  • to the left of 𝑝4=2p4=2 is 𝑝3=𝑝41=21=1p3=p4−1=2−1=1.
  • for all 𝑖i is 𝑝𝑖𝑖pi≠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

The first line of input data contains a single integer 𝑡t (1𝑡1041≤t≤104) — 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𝑛21052≤n≤2⋅105).

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 21052⋅105.

[Solution] Funny Permutation solution codeforces

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.
Example

input

Copy
5
4
3
7
5
2

output

Copy
3 4 2 1
-1
6 7 4 5 3 2 1
5 4 1 2 3
2 1

[Solution] Funny Permutation solution codeforces

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,2,3][1,3,2][1,3,2][2,1,3][2,1,3][3,2,1][3,2,1] have fixed points, and in [2,3,1][2,3,1] and [3,1,2][3,1,2] the first condition is met not for all positions.

Leave a Comment