分析
如果只能用操作 $1$，根据某个经典结论答案就是逆序对数。于是很容易想到 $\mathcal{O}(n^3\log n)$ 的暴力：枚举操作 $2$ 交换了哪两个位置，然后求逆序对即可。
考虑优化。因为每次只交换了两个位置，所以没有必要整个重新求一遍逆序对。假设交换了 $i$ 和 $j$，原来的逆序对数是 $A$，那么交换后的逆序对数 $A'$ 为
$$A+[p_j>p_i]-[p_i>p_j]+\sum_{x=i+1}^{j-1}\big([p_j>p_x]+[p_x>p_i]-[p_i>p_x]-[p_x>p_j]\big)$$
讨论一下：当 $p_i<p_j$ 时 $A'=A+1+2\sum_{x=i+1}^{j-1}[p_i<p_x<p_j]$；当 $p_i>p_j$ 时 $A'=A-1-2\sum_{x=i+1}^{j-1}[p_j<p_x<p_i]$。这样子就优化到了 $\mathcal{O}(n^3)$。
因为交换 $i<j,p_i<p_j$ 的 $i,j$ 一定不优，所以我们只要考虑交换 $i<j,p_i>p_j$ 的情况。
我们把排列中的每个数看成一个点 $(i,p_i)$，则 $\sum_{x=i+1}^{j-1}[p_j<p_x<p_i]$ 等于以 $(i,p_i)$ 为左上角、$(j,p_j)$ 为右下角的矩形中的点数。预处理二维前缀和后枚举 $i,j$ 即可做到 $\mathcal{O}(n^2)$。
再进一步发现，我们只会选择那些左上方没有点的 $(i,p_i)$ 和那些右下角没有点的 $(j,p_j)$，而满足条件的 $(i,p_i)$ 和 $(j,p_j)$ 一定满足 $p_i$ 随 $i$ 的增加而增加、$p_j$ 随 $j$ 的增加而增加。
再考虑有哪些矩形包含了 $x$。设 $l$ 为最小的 $p_i>p_x$ 的 $i$，$r$ 为最大的 $p_j<p_x$ 的 $j$，则 $i\in[l,x-1],j\in[x+1,r]$。我们把 $(i,j)$ 看成点的话，则它在以 $(l,x+1)$ 为左下角、$(x-1,r)$ 为右上角的矩形内。我们只要求被最多矩形覆盖的位置被覆盖的次数，直接扫描线+线段树即可。时间复杂度 $\mathcal{O}(n\log n)$。
上面算出的是 $\sum_{x=i+1}^{j-1}[p_j<p_x<p_i]$ 的最大值，记得要算出逆序对后减去两倍这个值才是答案。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=300000+10;
int n,h[N];
int sta1[N],top1,sta2[N],top2,vis[N];
struct node { int x,l,r,w; } q[N<<1]; int cnt=0;
bool operator <(node i,node j) {
return i.x!=j.x?i.x<j.x:i.w<j.w;
}
int find1(int x) {
int L=1,R=top1;
while (L<R) {
int mid=(L+R)>>1;
if (h[sta1[mid]]>h[x]) R=mid;
else L=mid+1;
}
return sta1[L];
}
int find2(int x) {
int L=1,R=top2;
while (L<R) {
int mid=(L+R)>>1;
if (h[sta2[mid]]<h[x]) R=mid;
else L=mid+1;
}
return sta2[L];
}
#define ls (o<<1)
#define rs (o<<1|1)
int maxv[N<<2],addv[N<<2];
void pushup(int o) { maxv[o]=max(maxv[ls],maxv[rs]); }
void pushdown(int o) {
if (addv[o]) {
addv[ls]+=addv[o],maxv[ls]+=addv[o];
addv[rs]+=addv[o],maxv[rs]+=addv[o];
addv[o]=0;
}
}
void modify(int o,int l,int r,int ql,int qr,int w) {
if (ql<=l&&r<=qr) { addv[o]+=w,maxv[o]+=w; return; }
int mid=(l+r)>>1; pushdown(o);
if (ql<=mid) modify(ls,l,mid,ql,qr,w);
if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
pushup(o);
}
#undef ls
#undef rs
int c[N];
void add(int x,int y) { for (;x<=n;x+=x&-x) c[x]+=y; }
int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }
int main() {
n=read();
for (int i=1;i<=n;++i) h[i]=read();
for (int i=1;i<=n;++i)
if (i==1||h[i]>h[sta1[top1]]) sta1[++top1]=i,vis[i]=1;
for (int i=n;i>=1;--i)
if (i==n||h[i]<h[sta2[top2]]) sta2[++top2]=i,vis[i]=1;
for (int i=1;i<=n;++i) {
if (vis[i]) continue;
int l=find1(i),r=find2(i);
if (l<i&&i<r)
q[++cnt]=(node){l,i+1,r,1},q[++cnt]=(node){i,i+1,r,-1};
}
sort(q+1,q+cnt+1); ll ans=0;
for (int i=1;i<=cnt;++i) {
modify(1,1,n,q[i].l,q[i].r,q[i].w);
if (q[i].x!=q[i+1].x) ans=max(ans,(ll)maxv[1]);
}
ans=-ans*2;
for (int i=1;i<=n;++i) add(h[i],1),ans+=i-sum(h[i]);
printf("%lld\n",ans);
return 0;
}