$n\le 3\times 10^5$。

信友队提高二班 Day3 C 题求助，大概是转化为二维数点然后扫描线，但是写挂了。

扫描线因为线段的端点处会重复，所以用了动态开点线段树。不知为何一直 70 pts

#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,L[N<<1],R[N<<1],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,cntx,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
*/