#include <bits/stdc++.h>
using namespace std;
typedef vector <int> vi;
typedef long long ll;
typedef pair <int, int> ii;
#define X first
#define Y second
#define mk make_pair
#define Rep(i, n) for(int i = 0; i < int(n); i ++)
const int MOD = (int) 1e9 + 7;
void MAIN();
int main(){
    //freopen("input.txt", "r", stdin);
    //freopen("buble.inp", "r", stdin);
    //freopen("buble.out", "w", stdout);
    MAIN();
    return 0;
}
//////////////////////////////////////////////////////////////////////////


const int N = 100004;

int n, a[N], bit[N], cnt[N];

void update(int i){
    for(; i < N; i += i & -i) bit[i] ++;
}

int get(int i){
    int res = 0;
    for(; i > 0; i -= i & -i) res += bit[i];
    return res;
}

ii x[N];
vi V[N];
vi se;
#define md (p+q>>1)

namespace ST{
    int t[N << 2], lz[N << 2];

    void update(int k, int p, int q, int x, int y, int z){
        if(p > y || q <= x) return;
        if(p >= x && q - 1 <= y){
            lz[k] += z;
            t[k] += z;
            return;
        }
        update(k*2+1, p, md, x, y, z);
        update(k*2+2, md, q, x, y, z);

        t[k] = max(t[2*k+1], t[2*k+2]) + lz[k];
    }

    int get(int beg){
        return t[0];
    }
}

int ck[N];
int m;

vector <ii> U[N];


void add(int i, int v){
    ck[i] = 2;
    int l = lower_bound(se.begin(), se.end(), i) - se.begin();
    int L = l, R = m;
    while(L < R){
        int mid = L + R + 1 >> 1;
        if(a[se[mid]] <= a[i]) L = mid;
        else R = mid - 1;
    }

    if(a[se[L]] <= a[i]){
        if(v == 1){
            L = l, R = m;
            while(L < R){
                int mid = L + R + 1 >> 1;
                if(a[se[mid]] < a[i]) L = mid;
                else R = mid - 1;
            }
            if(a[se[L]] >= a[i]) L --;
            ST:: update(0, 1, m + 1, l, L, 1);
            U[i].push_back(ii(l, L));

        } else if(v == 0){
            ST:: update(0, 1, m + 1, l, L, 1);
            U[i].push_back(ii(l, L));
        } else {
            ST:: update(0, 1, m + 1, l, L, 1);
            U[i].push_back(ii(l, L));

            L = l, R = m;
            while(L < R){
                int mid = L + R + 1 >> 1;
                if(a[se[mid]] < a[i]) L = mid;
                else R = mid - 1;
            }
            if(a[se[L]] >= a[i]) L --;
            ST:: update(0, 1, m + 1, l, L, 1);
            U[i].push_back(ii(l, L));
        }
    }
}

void del(int i){
    Rep(j, U[i].size()){
        ST:: update(0, 1, m + 1, U[i][j].X, U[i][j].Y, -1);
    }
}

ll inv = 0;

void MAIN(){
    scanf("%d", &n);
    Rep(i, n) scanf("%d", a+i);

    Rep(i, n) x[i] = ii(a[i], i);

    {
        sort(x, x+n);
        a[x[0].Y] = 1;
        for(int i = 1; i < n; i ++){
            a[x[i].Y] = a[x[i-1].Y];
            if(x[i].X > x[i-1].X) a[x[i].Y] ++;
        }

        bool inc = 1;
        for(int i = 1; i < n; i ++) if(a[i] <= a[i-1]) inc = 0;
        if(inc){
            printf("1\n");
            return;
        }


        for(int i = n-1; i >= 0; i --){
            inv += get(a[i] - 1);
            update(a[i]);
        }
    }

    {
        Rep(i, n) V[a[i]].push_back(i);

        se.push_back(-1);
        se.push_back(n-1);
        for(int i = n - 2; i >= 0; i --){
            if(a[i] < a[se.back()]) se.push_back(i);
        }
        sort(se.begin(), se.end());
    }

    m = se.size() - 1;

    int pre = 0, op = 0;
    int beg = 1;

    for(int i = 0; i < n; i ++){
        if(a[i] > pre){
            //cout << i << endl;
            for(int j = pre; j <= a[i]; j ++){
                Rep(k, V[j].size()){
                    int l = V[j][k];
                    if(l <= i) continue;
                    //cout << l << endl;
                    if(j == pre) add(l, 0);
                    else if(j == a[i]) add(l, 1);
                    else add(l, 2);
                }
            }

            while(beg <= m && se[beg] <= i) beg ++;
            if(beg <= m && a[i] > a[se[beg]]){
                op = max(op, ST:: get(i));
            }
            pre = a[i];
        }
        del(i);
    }

    cout << inv - op << endl;
}

Measured memory_bytes: 17248