考虑自然的图论模型，$n$ 个点，$i$ 连向 $a_i$。如果没有 $(j-i) > 1$，显然只需要 $n$ 减环长次操作就可以排序。注意到这个排序策略必须要每一次都环数 $+1$ 才行，也就是每一次操作都在环内。

当我们不能用环长 -1 次环内的不相邻交换操作排序，我们就称这个环是难的。认为自环不是难的，这样最终状态没有难的环。显然编号相邻的二元环是难的，所以有难的环。考察什么样的环是难的。

如果一个环在编号上占据的不是一段区间，那么它不是难的：假设存在一个 $l$ 不在环上且有 $>l$ 和 $<l$ 的点在环上，那么必然存在一条 $<l$ 到 $>l$ 的边，也存在一条 $>l$ 到 $<l$ 的边。任选其中一条边交换，可以让 $<l$ 或者 $>l$ 的点的个数减 1 并获得一个自环。一直做直到两边都剩一个点，这个时候交换它们俩就行了。

考虑值域连续的环，设其长度为 $l$。注意到若存在一个 $i \in [2,l-1]$ 它的位置不是 $i-1$ 或者 $i+1$，就可以通过把 $i$ 归位创造一个长度为 $(l-1)$ 的值域不连续的环。因此这样的环不是难的。

所以难的环一定有 $i \in [2,l-1]$ 的位置要么是 $i-1$ 要么是 $i+1$，即可以选左右。注意到若 $p$ 选右 $p+1$ 选左就会有二元环不符合这个环长条件，所以一定是一段前缀选左一段后缀选右，所以环长成 2 3 4 5 ... k n 1 (k+1) (k+2) ... (n-2) (n-1) 这个样子。

当这个环不是 2 3 4 5 ... (n-1) n 1 的时候，你总是可以通过归位最小或最大元素，把这个环归位成 2413，此时存在一个三步的做法：交换