找出性质 DP。好题！

结论：最终序列 $a$ 由若干个连续等差下降子段构成，其中公差为 $-1$。（对于上升的情况，我们可以认为是若干个长度为 $1$ 的下降子段）

考虑证明：首先 $a$ 是一个排列。注意到 $a_i+2\gt a_{i-1} \iff a_i\ge a_{i-1}-1$ 即可。

套路地，考虑设计一个 dp。设 $f(i)$ 为值域 $[1,i]$ 已经分成若干个连续下降子段（可以认为是放在结果序列 $a$ 的前 $i$ 个位置）的最小交换次数。套路地写出转移：

$$f(i)=\min _{j\in [0,i)} \{f(j)+\mathrm{calc}(j+1,i)\}$$

其中 $\mathrm{calc}(l,r)$ 表示将 $[l,r]$ 值域排列成一个连续下降子段的最小交换次数。

现在的序列中，位置 $[1,l)$ 已经被值域 $[1,l)$ 占据，所以 $[1,l)$ 已经被考虑过了，不能重复计算。我们只需要考虑 $[l,n]$ 这段值域，目标是：让值域 $[l,r]$ 占据位置 $[l,r]$。

以下默认 $1\le i\neq j\le n$。

我们可以认为，操作是这么进行的：先将值域为 $[l,r]$ 的数摆在位置 $[l,r]$，再交换使其变成下降的。

将值域为 $[l,r]$ 的数染成 $0$，值域为 $(r,n]$ 的数染成 $1$，我们要让 $0$ 占据位置 $[l,n]$ 的前一段，并且 $0$ 之间不互相交换。这部分答案就是 $0,1$ 之间的逆序对数。也就是：

$$\sum_{i=1}^n \sum_{j=i+1}^n [a_i\gt r][l\le a_j\le r]$$

最后，交换成下降序列，交换次数就是顺序对数，也就是：

$$\sum_{i=1}^n\sum_{j=i+1}^n [a_i\in [l,r]][a_j\in [l,r]][a_i\lt a_j]$$

朴素地实现 $\mathrm{calc}$ 可以获得 $44$ 分。注意到：这是一个二维数点问题。例如，对于顺序对 $(i,j)$，视为 $(a_i,a_j)$ 上有一个点，那么每次查询就是查询 $(l,l)$，$(r,r)$ 为顶点的正方形内的点的数量，可以二维前缀和维护。

这样，我们就做到了 $\Theta(n^2)$。代码。

#include <bits/stdc++.h>

using namespace std;

constexpr  int MAXN=5e3+10;
int a[MAXN], f[MAXN], n;
int g[MAXN][MAXN], h[MAXN][MAXN];

signed main() {
	cin>>n; for (int i=1; i<=n; ++i) cin>>a[i];
	for (int i=1; i<=n; ++i) 
	for (int j=i+1; j<=n; ++j) {
		g[min(a[i],a[j])][max(a[i],a[j])]+=a[i]<a[j],
		h[min(a[i],a[j])][max(a[i],a[j])]+=a[i]>a[j];
	}
	
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=n; ++j)
			g[i][j]+=g[i][j-1]+g[i-1][j]-g[i-1][j-1],
			h[i][j]+=h[i][j-1]+h[i-1][j]-h[i-1][j-1];
	
	memset(f,0x3f,sizeof f); f[0]=0;
	auto calc=[](int l, int r) {
		int ans=g[r][r]-g[l-1][r]-g[r][l-1]+g[l-1][l-1];
		if (r==n) return ans; 
		ans+=h[r][n]-h[r][r]-h[l-1][n]+h[l-1][r];
		return ans;
	}; 
	for (int i=1; i<=n; ++i) 
	for (int j=0; j<i; ++j)
		f[i]=min(f[i],f[j]+calc(j+1,i));
	cout<<f[n]<<'\n';
}