记一次选择位置 $i$ 的操作为 $F_i$。这个操作等价于翻转长度为 $i-1$ 的前缀，保持第 $i$ 个位置不动，再翻转长度为 $n-i$ 的后缀。

一个长度为 $m$ 的翻转，其置换奇偶性为 $\frac{m(m-1)}2$。因此 $F_i$ 的奇偶性为 $\frac{(i-1)(i-2)}2+\frac{(n-i)(n-i-1)}2$。

可以推出，当且仅当 $n\equiv 2\pmod 4$ 时，所有操作都是偶置换。

所以若 $n\equiv2\pmod4$，且所有数互不相同，那么只能完成偶置换。若存在两个相同的数，则可以交换这两个相同数在排序后对应的目标编号，从而改变目标置换的奇偶性，但最终得到的非降序列不变。

于是唯一无解的情况是：$n\equiv2\pmod4$，所有 $a_i$ 两两不同，并且当前序列到非降序序列的置换是奇置换。

接下来先把序列转化成排列。将所有位置按照 $(a_i,i)$ 排序，排序后第 $j$ 个元素的目标编号为 $j$。这样原序列就被转化成一个排列 $p$，其中 $p_i$ 表示当前位置 $i$ 上的数应该去往的目标位置。

如果序列中存在重复元素，并且需要改变奇偶性，只需要交换两个相同元素对应的目标编号即可。之后只需考虑如何把排列 $p$ 变成恒等排列。

当 $n\not\equiv2\pmod4$，并且当前排列为奇置换时，可以先执行一次奇操作，把排列奇偶性变成偶置换。具体来说：

• 若 $n\equiv0\pmod4$，选择位置 $1$；
• 若 $n\equiv1\pmod4$，选择位置 $2$；
• 若 $n\equiv3\pmod4$，选择位置 $1$。

执行后重新维护当前排列即可。

下面说明如何用原操作实现三元轮换。对于三个位置 $x<y<z$，连续执行 $F_x,F_{n-(y-x)+1},F_{z-y},F_z$，可以实现 $(A_x,A_y,A_z)\to(A_y,A_z,A_x)$，也就是对位置 $x,y,z$ 做一次三元轮换，其余位置不变。

如果反向执行这四次操作，则可以实现反方向的三元轮换，即 $(A_x,A_y,A_z)\to(A_z,A_x,A_y)$。因此可以实现任意三个不同位置上的三元轮换。

接下来用三元轮换排序偶置换。维护两个数组：$p_i$ 表示当前位置 $i$ 上元素的目标位置，$pos_x$ 表示目标位置为 $x$ 的元素当前所在位置。

从左到右扫描。如果 $p_i=i$，直接跳过。否则令 $j=pos_i,x=p_i$。若 $j\ne x$，则对位置 $(i,j,x)$ 做一次三元轮换，使得位置 $i$ 得到目标为 $i$ 的元素，位置 $x$ 得到目标为 $x$ 的元素。这样一次三元轮换至少可以固定两个位置。

剩下的一种情况是 $p_i=j,p_j=i$，也就是一组二元环。二元环不能单独用一次三元轮换解决，先把它保存下来。

由于当前排列是偶置换，二元环数量一定为偶数。对于两组二元环 $(a,b),(c,d)$，先对 $(a,b,c)$ 做一次三元轮换，再对 $(b,c,d)$ 做一次三元轮换，即可同时消去这两组二元环。

最后估计操作次数。每个三元轮换使用 $4$ 次原操作；普通三元轮换每次至少固定两个位置，两组二元环使用两次三元轮换固定四个位置。因此三元轮换次数不超过 $\frac n2$，原操作次数不超过 $2n$。

再加上可能预先执行的一次奇操作，总操作次数不超过 $2n+1$。由于 $n\le10^5$，所以 $2n+1\le 2\times10^5+1$，满足题目限制。

排序需要 $O(n\log n)$ 的时间，构造操作需要 $O(n)$ 的时间，因此总时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

---

本题的部分分主要按照 $n$ 的大小逐步放开。较小的数据用于鼓励选手直接搜索状态图，或者用 BFS / DFS 判断目标序列是否可达，从而观察到操作背后的排列性质。随着 $n$ 增大，暴力搜索不可行，选手需要转向研究操作对应的置换，并发现 $n\bmod 4$ 与置换奇偶性的关系。最后的满分数据要求选手不仅能判断是否有解，还要构造出不超过限制次数的操作序列，因此需要掌握用题目操作模拟三元轮换的构造方法。