非常好题目，第一步都想不出来。
可以观察出来最优方案必定是从大往小将 \(x\) 放到 \(x+1\) 前，有可能不动，中间的比他小的一定要放到前面去。考虑用 dp 计算最小值。
这里是这道题最重要的一步：相对位置的变化非常不好描述，考虑将所有数固定。一次操作改为：不影响其他其他数的位置，将一个数放到任意位置，一个位置上可能有多个数。稍微分析一下可以发现，如果从大到小考虑的话，那么一个数的实际位置就是在他之前的它小的数。这个实际位置的计算还是有些问题的，比如假设当前数是 \(x\) ，如果之前我们将一些数往前换的话，会将一些比 \(x\) 大的数放在 \(x\) 之前，从而影响 \(x\) 的实际位置，但是这种情况十分局限，我们可以直接在前面确定这些比 \(x\) 大的数放到的位置时计算 \(x\) 越过的比他大的数的个数。
有了这种计算方式，我们可以设计 \(dp\)，跟据我们之前推导的交换方法，我们可以设计 \(f_{i,j}\) 表示当前考虑完 \(i,i+1,\dots,n\)，且 \(i\) 放在位置 \(j\) 的最小代价，对于一个 \(i\)，我们有两种决策，第一种是将其放置在 \(i+1\) 的位置上。设原序列上 \(i\) 的位置是 \(j\)，\(i+1\) 的位置是 \(k\)，则若忽略那些大于 \(i\) 且在 \(i\) 之前的数，\(i\) 的实际位置是 \(\sum\limits_{t<j}{[a_t<a_i]+1}\)，\(i+1\) 位置同理，稍微修点细节可以得出转移：
\[f_{i,k} \leftarrow f_{i+1,k} + \sum\limits_{t<j}{[a_t<a_i]} + \sum\limits_{t<k}{[a_t<a_i]} + 2 \]我们考虑第二种决策，即不改变 \(i\) 的位置。此时我们需要考虑第一种转移时漏下的贡献，按照第一种转移时的定义，不难得出少算的贡献为 \(\sum\limits_{j<t<k}{[a_t<a_i](a_i-a_t)}\)，得出转移：
\[f_{i,j} \leftarrow f_{i+1,k} + \sum\limits_{j<t<k}{[a_t<a_i](a_i-a_t)} \]构造方案的话，倒推就行了。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+10,inf=0x3f3f3f3f;
int n,a[maxn],f[maxn][maxn],g[maxn][maxn],t[maxn],pos[maxn];
int sum[maxn][maxn],cnt[maxn][maxn];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],
t[i]=a[i];
sort(t+1,t+1+n);
for(int i=1;i<=n;i++)
{
a[i]=lower_bound(t+1,t+1+n,a[i])-t;
a[i]=n+1-a[i];
pos[a[i]]=i;
}
a[n+1]=n+1;
for(int i=1;i<=n+1;i++)
{
for(int j=1;j<=n+1;j++)sum[i][j]=sum[i-1][j],cnt[i][j]=cnt[i-1][j];
for(int k=a[i];k<=n+1;k++)sum[i][k]+=a[i],cnt[i][k]++;
}
memset(f,0x3f,sizeof f);
f[n+1][n+1]=0;
for(int x=n;x>=0;x--)
for(int q=n+1;q>=1;q--)
if(f[x+1][q]!=inf)
{
if(!x)continue;
int p=pos[x];
if(f[x][q]>f[x+1][q]+cnt[p-1][x-1]+cnt[q-1][x-1]+2)
g[x][q]=q,f[x][q]=f[x+1][q]+cnt[p-1][x-1]+cnt[q-1][x-1]+2;
if(p<q&&f[x][p]>f[x+1][q]+(cnt[q-1][x-1]-cnt[p][x-1])*x-(sum[q-1][x-1]-sum[p][x-1]))
g[x][p]=q,f[x][p]=f[x+1][q]+(cnt[q-1][x-1]-cnt[p][x-1])*x-(sum[q-1][x-1]-sum[p][x-1]);
}
vector< int > Ans;
int mn=inf,q=0;
for(int i=1;i<=n+1;i++)if(f[1][i]<mn)mn=f[1][i],q=i;
for(int x=1;x<=n;x++)Ans.push_back(q),q=g[x][q];
reverse(Ans.begin(),Ans.end());
vector< pair<int,int> > val;
for(int i=0;i<Ans.size();i++)
if(Ans[i]!=pos[n-i])
{
int pnow=pos[n-i],qnow=Ans[i];
int rp=cnt[pnow-1][n-i-1]+1,rq=cnt[qnow-1][n-i-1]+1;
for(int j=0;j<i;j++)rp+=Ans[j]<pnow;
for(int j=0;j<i;j++)rq+=Ans[j]<qnow;
if(rp==n+1)rp--;
if(rq==n+1)rq--;
val.push_back({rp,rq});
}
cout<<val.size()<<'\n';
for(auto [x,y]:val)cout<<x<<' '<<y<<'\n';
}