XOR Convenience (Easy Version)

Rewrite the requirement first:

$$p_i = p_j \oplus i$$

is equivalent to

$$p_i \oplus i = p_j.$$

For every constrained position $i$ with $2 \le i \le n-1$, position $n$ is always a legal choice for $j$, because $n \ge i$. So instead of finding a different witness $j$ for every $i$, we can make all of them use the same witness: $j=n$.

Let's set

$$p_n = 1.$$

Then for every $i=2,3,\dots,n-1$, we want

$$p_i \oplus i = 1.$$

XOR is reversible, and $i\oplus i=0$, so this is solved by

$$p_i = i \oplus 1.$$

This is very concrete: XORing by $1$ only flips the last bit. Therefore:

• if $i$ is even, $i\oplus 1=i+1$;
• if $i$ is odd, $i\oplus 1=i-1$.

So positions $2,3$ receive values $3,2$, positions $4,5$ receive $5,4$, and so on.

Now we only need to check that this is actually a permutation. We set $p_n=1$, and for $2\le i\le n-1$ we set $p_i=i\oplus1$.

If $n$ is even, then the positions $2,\dots,n-1$ produce exactly the values $2,3,\dots,n-1$. Together with $p_n=1$, the only missing value is $n$, so set $p_1=n$.

If $n$ is odd, then the positions $2,\dots,n-1$ produce the values $2,3,\dots,n$ except $n-1$. Together with $p_n=1$, the only missing value is $n-1$, so set $p_1=n-1$.

Position $1$ is not checked by the statement, so dumping the leftover value there is completely legal. No drama.

For correctness, take any $i$ such that $2\le i\le n-1$. By construction,

$$p_i=i\oplus1.$$

Then

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

Also $p_n=1$, so

$$p_i\oplus i=p_n.$$

Thus choosing $j=n$ satisfies the condition for this $i$. Since this works for every constrained $i$, the permutation is valid.

The construction is linear per test case. The total complexity is

$$O(n)$$

per test case, and

$$O\left(\sum n\right)$$

over all test cases. Memory usage is $O(n)$ if we store the answer, or $O(1)$ extra beyond output buffering.