#include<bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}

const int SIZE=100000;

struct segtree{
    static const int SEG=1<<17;
    vint ma,lazy;
    segtree(){
        ma.resize(SEG*2);
        lazy.resize(SEG*2);
    }
    void push(int k){
        ma[k]+=lazy[k];
        if(k<SEG-1){
            lazy[k*2+1]+=lazy[k];
            lazy[k*2+2]+=lazy[k];
        }
        lazy[k]=0;
    }
    void add(int a,int b,int x,int k=0,int l=0,int r=SEG){
        push(k);
        if(r<=a||b<=l)return;
        if(a<=l&&r<=b){
            lazy[k]+=x;
            push(k);
            return;
        }
        add(a,b,x,k*2+1,l,(l+r)/2);
        add(a,b,x,k*2+2,(l+r)/2,r);
        ma[k]=max(ma[k*2+1],ma[k*2+2]);
    }
    int get(int a,int b,int k=0,int l=0,int r=SEG){
        push(k);
        if(r<=a||b<=l)return 0;
        if(a<=l&&r<=b)return ma[k];
        return max(get(a,b,k*2+1,l,(l+r)/2),get(a,b,k*2+2,(l+r)/2,r));
    }
};

struct BIT{
    int N;
    vint dat;
    void init(int n){
        N=n;
        dat.resize(N+1);
    }
    void add(int k,int x){
        for(k++;k<=N;k+=k&-k)dat[k]+=x;
    }
    int sum(int k){
        int ret=0;
        for(k++;k;k-=k&-k)ret+=dat[k];
        return ret;
    }
};

int N;
int A[SIZE];

vint up,dw,el;
vint l,r;

vint press;
signed main(){
    scanf("%lld",&N);
    rep(i,N)scanf("%lld",&A[i]);


    //compress
    rep(i,N)press.pb(A[i]);
    sort(all(press));
    press.erase(unique(all(press)),press.end());
    rep(i,N)A[i]=lower_bound(all(press),A[i])-press.begin();


    rep(i,N){
        if(up.size()==0||A[up.back()]<A[i])up.pb(i);
        while(dw.size()&&A[dw.back()]>=A[i])dw.pop_back();
        dw.pb(i);
    }

    rep(i,N){
        if(!binary_search(all(up),i)&&!binary_search(all(dw),i)){
            el.pb(i);
            int lb=-1,ub=up.size();
            while(ub-lb>1){
                int mid=(ub+lb)/2;
                if(A[up[mid]]>=A[i])ub=mid;
                else lb=mid;
            }
            l.pb(ub);
            r.pb(lower_bound(all(up),i)-up.begin());
        }
    }

    //get base
    BIT bit;bit.init(N+114);
    int base=0;
    rep(i,N){
        int x=bit.sum(A[i]);
        base+=i-x;
        bit.add(A[i],1);
    }
    if(base==0){
        bool isok=false;
        rep(i,N-1)if(A[i]==A[i+1])isok=true;
        if(isok)puts("0");
        else puts("1");
        return 0;
    }
    //rep(i,up.size())cout<<up[i]+1<<" ";cout<<endl;
    //rep(i,dw.size())cout<<dw[i]+1<<" ";cout<<endl;
    //rep(i,el.size())cout<<el[i]+1<<" ";cout<<endl;
    //rep(i,el.size())cout<<l[i]<<" "<<r[i]<<endl;

    int cur=0;
    segtree seg;
    priority_queue<pint,vector<pint>,greater<pint> >que;
    int ll=0,rr=0,ma=0;
    rep(i,dw.size()){
        while(cur<el.size()&&el[cur]<dw[i]){
            seg.add(l[cur],r[cur],2);
            if(A[up[l[cur]]]==A[el[cur]])seg.add(l[cur],l[cur]+1,-1);
            que.push(pint(A[el[cur]],cur));
            //cout<<el[cur]<<" is in :";rep(i,up.size())cout<<seg.get(i,i+1)<<" ";cout<<endl;
            cur++;
        }


        vint same;
        while(que.size()&&que.top().fi<A[dw[i]]){
            int j=que.top().se;que.pop();
            seg.add(l[j],r[j],-2);
            if(A[up[l[j]]]==A[el[j]])seg.add(l[j],l[j]+1,1);
        }
        while(que.size()&&que.top().fi==A[dw[i]]){
            int j=que.top().se;que.pop();
            seg.add(l[j],r[j],-1);
            same.pb(j);
        }

        while(ll<up.size()&&A[up[ll]]<=A[dw[i]])ll++;
        while(rr<up.size()&&up[rr]<dw[i])rr++;
        chmax(ma,seg.get(ll,rr)+1);


        rep(j,same.size()){
            int k=same[j];
            seg.add(l[k],r[k],1);
            seg.add(l[k],r[k],-2);
            if(A[up[l[k]]]==A[el[k]])seg.add(l[k],l[k]+1,1);
        }
    }

    printf("%lld\n",base-ma);
    return 0;
}

//6 1 1 2 2 1 2
//7 4 5 4 7 1 3 2

Measured memory_bytes: 13400