C++(clang++ 11.0.1) 解法, 执行用时: 79ms, 内存消耗: 12388K, 提交时间: 2023-01-07 16:31:30

#include<bits/stdc++.h>
using namespace std;
namespace IO{
	template<typename T>inline bool read(T &x){
		x=0;
		char ch=getchar();
		bool flag=0,ret=0;
		while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
		while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
		x=flag?-x:x;
        return ret;
	}
	template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
	    return read(a)&&read(args...);
	}
	template<typename T>void prt(T x){
		if(x>9) prt(x/10);
		putchar(x%10+'0');
	}
	template<typename T>inline void put(T x){
		if(x<0) putchar('-'),x=-x;
		prt(x);
	}
	template<typename T>inline void put(char ch,T x){
		if(x<0) putchar('-'),x=-x;
		prt(x);
		putchar(ch);
	}
	template<typename T,typename ...Args>inline void put(T a,Args ...args){
	    put(a);
		put(args...);
	}
	template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
	    put(ch,a);
		put(ch,args...);
	}
	inline void put(string s){
		for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
	}
	inline void put(const char* s){
		for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
	}
}
using namespace IO;
#define N 300005
#define ll long long
int n,w[N],b[N],m,posl[N],posr[N],vall[N],valr[N],tl,tr;
template<typename T>struct BIT{
	#define lowbit(x) (x&-x)
	T c[N];
	inline void update(int x,T v){
		for(;x<=m;x+=lowbit(x)) c[x]+=v;
	}
	inline T query(int x){
		T res=0;
		for(;x;x^=lowbit(x)) res+=c[x];
		return res;
	}
	#undef lowbit
};
BIT<int> B;
template<typename T>struct Segment{
	T t[N<<2],lz[N<<2];
	#define lc(x) (x<<1)
	#define rc(x) (x<<1|1)
	inline void push_up(int x){
		t[x]=max(t[lc(x)],t[rc(x)]);
	}
	inline void push_down(int x){
		if(!lz[x]) return;
		t[lc(x)]+=lz[x],t[rc(x)]+=lz[x];
		lz[lc(x)]+=lz[x],lz[rc(x)]+=lz[x];
		lz[x]=0;
	}
	inline void update(int x,int l,int r,int ql,int qr,T val){
		if(ql<=l&&qr>=r) return t[x]+=val,lz[x]+=val,void();
		push_down(x);
		int mid=l+r>>1;
		if(ql<=mid) update(lc(x),l,mid,ql,qr,val);
		if(qr>mid) update(rc(x),mid+1,r,ql,qr,val);
		push_up(x);
	}
	#undef lc
	#undef rc
};
Segment<ll> T;
ll ans=2e18,sum;
struct Line{
	int l,r,val;
	Line(int _l=0,int _r=0,int _val=0):l(_l),r(_r),val(_val){}
};
vector<Line> g[N];
int main(){
	read(n);
	for(int i=1;i<=n;i++) read(w[i]),b[i]=w[i];
	sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++) w[i]=lower_bound(b+1,b+m+1,w[i])-b; 
	for(int i=1;i<=n;i++)
		sum+=B.query(m)-B.query(w[i]),B.update(w[i],1);
	if(!sum) return puts(m!=n?"0":"1"),0;
	for(int i=1;i<=n;i++)
		if(!tl||w[i]>vall[tl]) posl[++tl]=i,vall[tl]=w[i];
	for(int i=n;i;i--)
		if(!tr||w[i]<valr[tr]) posr[++tr]=i,valr[tr]=w[i];
	reverse(posr+1,posr+tr+1),reverse(valr+1,valr+tr+1);
	for(int i=1;i<=n;i++){
		int lx=lower_bound(vall+1,vall+tl+1,w[i])-vall;
		int ly=lower_bound(posl+1,posl+tl+1,i)-posl-1;
		int rx=upper_bound(posr+1,posr+tr+1,i)-posr;
		int ry=upper_bound(valr+1,valr+tr+1,w[i])-valr-1;
		if(lx>ly||rx>ry) continue;
		if(vall[lx]==w[i]&&valr[ry]==w[i]){
			g[lx].emplace_back(rx,ry-1,1);
			g[lx+1].emplace_back(rx,ry-1,-1); 
			g[lx+1].emplace_back(ry,ry,1);
			g[ly+1].emplace_back(ry,ry,-1);
			lx++,ry--;
		}else if(vall[lx]==w[i]){
			g[lx].emplace_back(rx,ry,1);
			g[lx+1].emplace_back(rx,ry,-1);
			lx++;
		}else if(valr[ry]==w[i]){
			g[lx].emplace_back(ry,ry,1);
			g[ly+1].emplace_back(ry,ry,-1);
			ry--;
		}
		if(lx<=ly&&rx<=ry)
			g[lx].emplace_back(rx,ry,2),
			g[ly+1].emplace_back(rx,ry,-2);
	}
	for(int i=1;i<=tl;i++){
		for(auto tmp:g[i]) T.update(1,1,tr,tmp.l,tmp.r,tmp.val);
		ans=min(ans,sum-T.t[1]-1);
	}
	put('\n',ans);
	return 0;
}