Notice that the first element of the permutation (`perm[0]`) can be derived by XOR-ing all elements in the `encoded` array with the XOR of all numbers from 1 to `n`. Start by computing `total_xor = 1 ^ 2 ^ ... ^ n` and then compute `perm[0] = total_xor ^ (encoded[0] ^ encoded[1] ^ ... ^ encoded[n-2])`.

Once you have `perm[0]`, reconstruct the rest of the permutation iteratively using the property `perm[i+1] = perm[i] ^ encoded[i]`. This works because `encoded[i] = perm[i] ^ perm[i+1]`, so XOR-ing `perm[i]` with `encoded[i]` gives `perm[i+1]`.

To optimize, compute `total_xor` efficiently using the formula for XOR of the first `n` numbers: if `n % 4 == 0`, `total_xor = n`; if `n % 4 == 1`, `total_xor = 1`; if `n % 4 == 2`, `total_xor = n + 1`; else `total_xor = 0`. Then, compute `perm[0]` as `total_xor ^ (encoded[0] ^ encoded[1] ^ ... ^ encoded[n-2])` and proceed with the iterative reconstruction.