rt，大致思路就是转化成二维数点，然后扫描线。但是扫描线会有重复的点，所以用了动态开点线段树。可是 WA $70pts$。不知道哪里错了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N=3e5+1;
int n,a[N],num,b[N],cntx,cnty,tots,mx[N*20],add[N*20],ans,ls[N*20],rs[N*20],node,rt;
pii p[N],px[N],py[N];
bool use[N];
struct seg{
int l,r,y,v;
}g[N];
void merge(int l,int r){
if(l^r){
int mid=(l+r)>>1;
merge(l,mid);
merge(mid+1,r);
int i=l,j=mid+1,cnt=l-1;
while(i<=mid&&j<=r){
if(a[i]<=a[j]){
b[++cnt]=a[i++];
}else{
num+=mid-i+1;
b[++cnt]=a[j++];
}
}
while(i<=mid){
b[++cnt]=a[i++];
}
while(j<=r){
b[++cnt]=a[j++];
}
for(int i=l;i<=r;++i){
a[i]=b[i];
}
}
}
void modify(int&x,int l,int r,int ql,int qr,int v){
if(!x){
x=++node;
}
if(ql<=l&&r<=qr){
mx[x]+=v;
add[x]+=v;
}else{
int mid=(l+r)>>1;
if(ql<=mid){
modify(ls[x],l,mid,ql,qr,v);
}else{
modify(rs[x],mid+1,r,ql,qr,v);
}
mx[x]=max(mx[ls[x]],mx[rs[x]])+add[x];
}
}
signed main(){
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
p[i]={i,a[i]};
}
merge(1,n);
for(int i=1,mx=0;i<=n;++i){
if(mx<p[i].se){
px[++cntx]=p[i];
mx=max(mx,p[i].se);
use[i]=1;
}
}
for(int i=n,mn=1e9;i;--i){
if(mn>p[i].se){
py[++cnty]=p[i];
mn=min(mn,p[i].se);
use[i]=1;
}
}
reverse(py+1,py+1+cnty);
for(int i=1;i<=n;++i){
if(!use[i]){
int l=1,r=cntx,f,f1,f2,f3;
while(l<=r){
int mid=(l+r)>>1;
if(px[mid].fi<p[i].fi&&px[mid].se>p[i].se){
f=mid;
r=mid-1;
}else{
l=mid+1;
}
}
l=f;
r=cntx;
while(l<=r){
int mid=(l+r)>>1;
if(px[mid].fi<p[i].fi&&px[mid].se>p[i].se){
f1=mid;
l=mid+1;
}else{
r=mid-1;
}
}
l=1;
r=cnty;
while(l<=r){
int mid=(l+r)>>1;
if(py[mid].fi>p[i].fi&&py[mid].se<p[i].se){
f2=mid;
r=mid-1;
}else{
l=mid+1;
}
}
f3=f2;
while(l<=r){
int mid=(l+r)>>1;
if(py[mid].fi>p[i].fi&&py[mid].se<p[i].se){
f3=mid;
l=mid+1;
}else{
r=mid-1;
}
}
g[++tots]={f,f1,f2,1};
g[++tots]={f,f1,f3,-1};
}
}
sort(g+1,g+1+tots,[](seg u,seg v){return u.y^v.y?u.y<v.y:u.v>v.v;});
for(int i=1;i<=tots;++i){
modify(rt,1,n,g[i].l,g[i].r,g[i].v);
ans=max(ans,mx[rt]<<1);
}
cout<<num-ans;
return 0;
}
/*
5
3 5 4 1 2
*/