# NAS_2523 - Editorial

Author: moonlight_cl25
Tester and Editorialist: iceknight1093

1158

None

# PROBLEM:

Given N, find the lexicographically maximum permutation P of \{1, 2, \ldots, N\} such that \gcd(P_1, P_3, \ldots) \gt \gcd(P_2, P_4, \ldots); or claim that none exist.

# EXPLANATION:

If N is even, the answer is just [N, N-1, \ldots, 3, 2, 1]; i.e, the numbers from 1 to N in descending order.
Itâ€™s easy to see that this satisfies the condition:

• \gcd(P_1, P_3, P_5, \ldots, P_{N-1}) = \gcd(N, N-2, N-4, \ldots, 4, 2) = 2, since all these numbers are even.
• \gcd(P_2, P_4, \ldots, P_N) = 1 since P_1 = 1.
• This is the lexicographically maximum permutation.

If N is odd, the answer is -1: no valid permutation exists.

Proof

We want \gcd(P_1, P_3, \ldots) \gt \gcd(P_2, P_4, \ldots); in particular \gcd(P_1, P_3, \ldots) \gt 1 must be true.
So, there should be some integer k\gt 1 that divides all integers placed at odd positions.

There are \left \lceil \frac{N}{2} \right\rceil odd positions, and the numbers placed there need to be distinct.
So, at the very least we need integers k, 2k, 3k, 4k, \ldots, k\cdot \left \lceil \frac{N}{2} \right\rceil to be \leq N.

However, this is not possible for k \gt 1, and we reach a contradiction.
So, no valid permutation exists.

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
if n%2 == 1: print(-1)
else: print(*list(reversed(range(1, n+1))))