Fun Permutation

The trick is to stop overthinking the GCD condition.

We need a permutation $q$ such that for every adjacent pair:

$$\gcd(p_i+q_i,\ p_{i+1}+q_{i+1}) \ge 3.$$

At first glance, this looks like we need to carefully arrange $q$ so each neighboring pair has some common factor. That sounds annoying. Luckily, there is a much cleaner way: make all the sums equal.

Key Idea

If we can force

$$p_i+q_i = S$$

for every position $i$, then every adjacent pair becomes:

$$\gcd(S,S)=S.$$

So we just need $S \ge 3$.

Now the question becomes: can we choose $q_i$ so that every $p_i+q_i$ equals the same constant?

Yes. Use:

$$q_i = n+1-p_i.$$

Then:

$$p_i+q_i = p_i+(n+1-p_i)=n+1.$$

So every sum is exactly $n+1$.

Since $n \ge 2$, we have:

$$n+1 \ge 3.$$

Therefore:

$$\gcd(p_i+q_i,\ p_{i+1}+q_{i+1}) = \gcd(n+1,n+1)=n+1 \ge 3.$$

Condition nuked. Done.

Why is $q$ a valid permutation?

Because $p$ contains every number from $1$ to $n$ exactly once.

The transformation

$$x \mapsto n+1-x$$

also maps the set $\{1,2,\dots,n\}$ to itself:

• $1$ becomes $n$
• $2$ becomes $n-1$
• $\dots$
• $n$ becomes $1$

No duplicates appear, and no value goes outside the range. So $q$ is also a permutation of size $n$.

Algorithm

For each test case:

1. Read $n$ and permutation $p$.
2. For each position $i$, output:

$$q_i = n+1-p_i.$$

That’s it. This problem is basically asking for the complement permutation, wearing a fake mustache labeled “number theory.”

Complexity

For each test case, we process the permutation once.

$$O(n)$$

time per test case, and

$$O(1)$$

extra memory besides the input/output.