官方题解。来源：清华大学学生算法协会仓库

考虑自然的图论模型，$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，此时存在一个三步的做法：交换 23 之后交换 24 和 13。

而当这个环是 2 3 4 5 ... (n-1) n 1 的时候，我们归纳证明其是难的。$n=2$ 显然是难的，因为交换不了。对于更大的 $n$，任意交换环上的两个元素会得到两个环，而之后必须要两个环都不是难的才能在 $n-1$ 次操作内排好序。但注意到交换了 $a_i=(i+1)$ 和 $a_j$ 之后，$a_{i+1} \sim a_j$ 就是 $i+2\ i+3\ \cdots\ j\ i+1$ 恰好构成一个长度为 $j-i \ge 2$ 的由归纳假设是难的环。所以第一步怎么做最后都会有一个难的环，所以这个环也是难的。

对于不难的环我们直接排到对应位置，对于难的环我们不能直接排好，需要用一些额外的操作来搞定。因为一次把两个环合并成一个，会导致总步数+2，同时最多删掉两个难环，因此答案下界是 $n$ 减环数加上（难环数量除 2 上取整乘二）。

这个下界是容易达到的：先把所有难环都弄成二元环，简单环排好，然后对于 2143，先交换 23 得到 3142，这个环不是难的，直接弄就行了。单独剩下一个 12 的情况，$n \ge 5$ 的时候总可以找到一个不相邻的位置，用三步操作归位。$n \le 4$ 的情况需要特判，小点全都暴力就行了。