限制极强，所以思考正解的结构。首先 $1,2,\dots,n$ 一定是可行的。然后 $1$ 的位置显然只能是 $1$ 或 $2$。我们猜测 $x$ 一定不能距离第 $x$ 个位置太远。考虑归纳，如果现在 $p_{1,2,\dots,x}$ 是 $\{1,2,\dots, x\}$ 的排列，那么设 $x+1$ 的位置是 $k$，$p_{k-1}\ge x+2$，得到 $k\le x+2$，所以 $k\in \{x+1,x+2\}$，所以我们得到关键结论：答案一定是 $1,2,\dots, n$ 通过交换若干组不同的相邻对 $i, i+1$ 得到的，然后显然这样的排列也是一定合法的。

那么先求出变为 $1,2,\dots,n$ 的代价，这个就是逆序对，然后考虑如果 $i$ 出现在 $i+1$ 后面，可以不交换 $i, i+1$ 从而减少一个逆序对，相当于对于每个 $i$ 在 $i+1$ 后面的 $i$，可以选择 $i, i+1$ 并使答案减少 $1$，每个数最多减一次。于是直接 DP 或贪心即可，时间复杂度 $\mathcal{O}(n\log n)$。