#include<stdio.h>
#include<algorithm>
using namespace std;
int b[110000];
int z[110000];
long long bit[110000];
long long sum(int a,int b){
	if(a)return sum(0,b)-sum(0,a-1);
	long long ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[b];
	return ret;
}
void add(int a,int b){
	for(;a<110000;a|=a+1)bit[a]+=b;
}
int segtree[262144];
int lx[110000];
int ly[110000];
int rx[110000];
int ry[110000];
void add2(int a,int b,int c,int d,int e,int f){
	if(d<a||b<c)return;
	if(c<=a&&b<=d){
		segtree[e]+=f;
	}else{
		add2(a,(a+b)/2,c,d,e*2,f);
		add2((a+b)/2+1,b,c,d,e*2+1,f);
	}
	if(e>1&&((segtree[e]!=0&&segtree[e^1]!=0)||segtree[e]>0||segtree[e^1]>0)){
		int t=max(segtree[e],segtree[e^1]);
		segtree[e/2]+=t;
		segtree[e^1]-=t;
		segtree[e]-=t;
	}
}
int query(int a,int b,int c,int d,int e,int f){
	if(d<a||b<c)return -99999999;
	if(c<=a&&b<=d)return segtree[e]+f;
	return max(query(a,(a+b)/2,c,d,e*2,f+segtree[e]),query((a+b)/2+1,b,c,d,e*2+1,f+segtree[e]));
}
int L[110000];
int R[110000];
pair<int,int>yp[110000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",b+i);
	bool chk=true;
	bool same=false;
	for(int i=0;i<a-1;i++)if(b[i]<b[i-1])chk=false;
	for(int i=0;i<a-1;i++)if(b[i]==b[i-1])same=true;
	if(chk){
		if(same)printf("0\n");
		else printf("1\n");return 0;
	}
	for(int i=0;i<a;i++){
		z[i]=b[i];
		yp[i]=make_pair(b[i],i);
	}
	std::sort(yp,yp+a);
	std::sort(z,z+a);
	long long ans=0;
	for(int i=0;i<a;i++){
		int at=lower_bound(z,z+a,b[i])-z;
		if(at<a-1)ans+=sum(at+1,a-1);
		add(at,1);
	}
	int tmp=0;
	int ls=0;
	int rs=0;
	for(int i=0;i<a;i++){
		if(tmp<b[i]){
			L[i]=1;
			tmp=b[i];
			lx[ls]=i;
			ly[ls++]=tmp;
		}
	}
	tmp=1000000007;
	for(int i=a-1;i>=0;i--){
		if(tmp>b[i]&&L[i]==0){
			R[i]=1;
			tmp=b[i];
		}
	}
	for(int i=0;i<a;i++){
		if(R[i]){
			rx[rs]=i;
			ry[rs++]=b[i];
		}
	}
	int ret=0;
	int rm=0;
	int ypat=0;
	for(int i=0;i<a;i++){
		if(R[i]){
			int nx=b[i];
			int tmp=0;
			while(ypat<a&&yp[ypat].first<nx){
				int ind=yp[ypat].second;
				if(!L[ind]&&!R[ind]){
					int to=lower_bound(ly,ly+ls,b[ind])-ly;
					int rim=lower_bound(lx,lx+ls,ind)-lx-1;
					if(to<=rim)add2(0,131071,to,rim,1,-1);
					if(b[ind]==ly[to])to++;
					if(to<=rim)add2(0,131071,to,rim,1,-1);
				}
				ypat++;
			}
			int cp=ypat;
			while(cp<a&&yp[cp].first==nx){
				int ind=yp[cp].second;
				if(!L[ind]&&!R[ind]){
					int to=lower_bound(ly,ly+ls,b[ind])-ly;
					int rim=lower_bound(lx,lx+ls,ind)-lx-1;
					if(to<=rim)add2(0,131071,to,rim,1,-1);

				}
				cp++;
			}			
			int at=lower_bound(lx,lx+ls,i)-lx-1;
			int at2=upper_bound(ly,ly+ls,b[i])-ly;
			if(at2<=at){
				tmp=query(0,131071,at2,at,1,0);
				ret=max(ret,tmp);
			}
			while(ypat<a&&yp[ypat].first==nx){
				int ind=yp[ypat].second;
				if(!L[ind]&&!R[ind]){
					int to=lower_bound(ly,ly+ls,b[ind])-ly;
					int rim=lower_bound(lx,lx+ls,ind)-lx-1;
					if(b[ind]==ly[to])to++;
					if(to<=rim)add2(0,131071,to,rim,1,-1);
				}
				ypat++;
			}		
		}else if(!L[i]){
			int to=lower_bound(ly,ly+ls,b[i])-ly;
			int rim=lower_bound(lx,lx+ls,i)-lx-1;
			if(to<=rim)add2(0,131071,to,rim,1,1);
			if(b[i]==ly[to])to++;
			if(to<=rim)add2(0,131071,to,rim,1,1);
		}

	}
//	printf("%lld %d\n",ans,ret);
	printf("%lld\n",ans-ret-1);
}

Measured memory_bytes: 6588