Power Permutation (Lösungsbesprechung)

Solution

The parity of the expression p_i^{p_{i+1}} depends only on $p_i$ i.e. p_i^{p_{i+1}} \equiv p_i (\bmod p_i) thus the problem reduces to for which $n$ that's the count of evens and odds in range [1,n-1] is equal and this happens only whe n $n$ is odd and in that case the order of the permutation doesn't matter , otherwise if $n$ is even then there's no valid option.

for _ in range(int(input())):
   n=int(input())
   if(n%2==0):
      print(-1)
   else:
      print(*[i for i in range(1,n+1)])

Complexity $\mathcal{O}(n)$