XOR-convenience (Hard Version)

Rewrite the condition as: for each $i<n$, the value $p_i\oplus i$ must appear at some position $j>i$. The witness cannot be $i$ itself because $i>0$, so $p_i\oplus i\ne p_i$.

The key trick is that witnesses may be reused. If we put $1$ at the last position, then any position $i$ can point to it by setting

$p_i=1\oplus i=i\oplus1.$

This swaps adjacent values:

$2\oplus1=3,\quad 3\oplus1=2,\quad 4\oplus1=5,\quad 5\oplus1=4.$

So the pattern $3,2,5,4,7,6,\ldots$ is not magic; it is just a bunch of positions pointing to the final $1$.

First handle odd $n$. Use

$p=[n-1,3,2,5,4,7,6,\ldots,n,1].$

Formally:

• $p_1=n-1$;
• for $2\le i<n$, set $p_i=i\oplus1$;
• $p_n=1$.

This is a permutation. The map $i\mapsto i\oplus1$ on $2,3,\ldots,n-1$ gives all values from $2$ to $n$ except $n-1$; then $p_1$ supplies $n-1$, and $p_n$ supplies $1$.

Now verify the condition. For $i=1$, use the position containing $n$:

$n\oplus1=n-1=p_1,$

because $n$ is odd. For every $2\le i<n$, use $j=n$:

$p_n\oplus i=1\oplus i=i\oplus1=p_i.$

So every odd $n$ works.

Now prove when the answer is impossible. Suppose $n$ is a power of two. If value $n$ appears at some position $i<n$, then its required witness would be

$n\oplus i=n+i>n,$

because $i$ only uses lower bits. That value is outside the permutation, impossible. Therefore value $n$ must be at position $n$.

Look at position $n-1$. Its only later position is $n$, so we would need

$p_{n-1}=p_n\oplus(n-1)=n\oplus(n-1)=2n-1,$

also outside $[1,n]$. Contradiction. So powers of two are dead. No cute escape hatch there.

It remains to construct even non-powers of two. Let

$x=\operatorname{lowbit}(n),$

so $x$ is the smallest set bit of $n$. Since $n$ is even and not a power of two, $2\le x<n$.

Define the permutation like this:

$$p_1=x+1,$$ $$p_i=i\oplus1\quad (2\le i<x),$$ $$p_x=n,$$ $$p_{x+1}=x,$$ $$p_i=i\oplus1\quad (x+2\le i<n),$$ $$p_n=1.$$

Empty ranges are fine.

Why is this a permutation? The normal ranges are complete adjacent swaps, so they use exactly their own values. The special positions $1,x,x+1,n$ use the special values $x+1,n,x,1$. Together, every value from $1$ to $n$ appears exactly once.

Now verify the condition.

For every normal position, $p_i=i\oplus1$, so it points to the final $1$:

$p_n\oplus i=1\oplus i=p_i.$

For $i=1$, use position $x+1$, where $p_{x+1}=x$:

$x\oplus1=x+1=p_1.$

For $i=x+1$, use the final position:

$1\oplus(x+1)=x=p_{x+1}.$

For $i=x$, we need a later value $y$ such that $y\oplus x=n$. Since $x$ is the lowest set bit of $n$, flipping bit $x$ changes $n$ to $n-x$, so choose

$y=n-x.$

This value appears later in the normal swapped suffix. More precisely, $n-x$ is even, and at position

$j=n-x+1$

we have

$p_j=j\oplus1=(n-x+1)\oplus1=n-x.$

Also $j>x$, because $n/x$ is an odd integer at least $3$. Therefore this witness is in the suffix, and

$(n-x)\oplus x=n=p_x.$

So all even non-powers work, and only powers of two fail.

Algorithm:

1. If $n$ is a power of two, print $-1$.
2. Else if $n$ is odd, print the odd construction.
3. Else compute $x=n\&(-n)$ and print the even construction.

The complexity is $O(n)$ per test case for output, and $O(1)$ extra memory if printed directly, or $O(n)$ if stored first for cleaner code.