提供一个更有趣的做法，注意下面虽然提到了随机，但是只是方便理解，这是确定性做法。
有解的充要可以通过打表之类的得出：顺序对数量是偶数。这是因为每次交换都会改变逆序对数量的奇偶性，所以答案和逆序对数的奇偶性和 $n(n-1)/2$ 的奇偶性有关，优雅地总结一下就是「顺序对数量是偶数」。
首先你应该很快就能想出一个贪心：设 $q=p^{-1}$，每次取出一个最小的 $q_i\neq i$，我们肯定是想要将值（不是下标） $i$ 与 $q_j=i$ 的值 $j$ 交换位置。但是在此之前，我们需要将 $i$ 与除了 $j$ 以外的每一个值都交换一遍，以满足题目要求「每对数被交换恰好一次」的条件，最后再与 $j$ 交换。此时问题变成一个子问题，继续做就好了。
不难发现当输入是一个 $1,2,\cdots,n$ 时上面的做法失效了。不妨先对拍一下，造数据时保证不生成 $1\sim n$ 这种极端输入，发现拍了好久才卡掉，这时候我们再 shuffle 一下，不一定是每次取出最小的 $i$，而是随机取一个 $q_i\neq i$ 的 $i$，发现根本卡不掉。
所以我们自然就会想到似乎只需要考虑输入是 $1\sim n$ 的情况就好了，事实上也是如此。这是因为我们上述贪心只有在某个子问题中取不到任何一个 $q_i\neq i$ 时才会失效，这时候这个子问题其实就是等价于一个 $1\sim n$ 的问题。只要我们做出来了这个特殊情况，就算上面不 shuffle，也能跑出正确解。
故考虑 $p=\{1,2,\cdots,n\}$。
此时根据我们的猜想，大部分情况下贪心是对的，不难想到扰乱一下 $p$，然后在下面的贪心中，如果用到了扰乱时用的操作，就不交换，继续做下去。如此贪心，或许就能够跑出解法？
如果此时我们将 $1$ 和 $2$ 交换，会发现似乎不行，这是因为最后无论如何我们都要将 $1$ 和 $2$ 交换回去，也就是无论如何都要用到 ban 掉的那个操作。
所以我们希望 $1$ 最后能和某个没有和他操作过的数互换位置，此时答案呼之欲出，先将值 $1$ 和 $2$ swap，再将值 $2$ 和 $3$ swap，此时 $p_1=3,p_2=1,p_3=2$，也就是我们操作过程中只会交换值 $1$ 和 $3$，而这个操作我们没有 ban 过，好像是对的？
写完就过了。正确性其实手模一下就可以了，因为我们只 ban 了 $(1,2)$ 和 $(2,3)$，手模前两轮发现是对的，那么后面的若干轮都没被 ban 过，所以归纳之后自然也是对的。