#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
 
#define MAX_N (100000)
 
using namespace std;
 
typedef long long lint;
 
lint bit[MAX_N + 1];
 
void add(int pos)
{
	for (; pos <= MAX_N; pos += pos & -pos)
		bit[pos] += 1;
}
 
lint sum(int pos)
{
	lint ret = 0;
	for (; pos; pos &= (pos - 1))
		ret += bit[pos];
	
	return (ret);
}
 
lint segAdd[1 << 18], segMax[1 << 18];
 
void add(int a, int b, lint x, int k = 0, int l = 0, int r = 1 << 17)
{
	if (b <= l || r <= a) return;
	
	if (a <= l && r <= b){
		segAdd[k] += x;
		while (k){
			k = (k - 1) / 2;
			segMax[k] = max(segMax[k * 2 + 1] + segAdd[k * 2 + 1],
							segMax[k * 2 + 2] + segAdd[k * 2 + 2]);
		}
		return;
	}
	
	add(a, b, x, k * 2 + 1, l, (l + r) / 2);
	add(a, b, x, k * 2 + 2, (l + r) / 2, r);
}
 
int main()
{
	int N;
	int A[MAX_N];
	
	scanf("%d", &N);
	
	for (int i = 0; i < N; i++){
		scanf("%d", A + i);
	}
	vector<int> X(A, A + N);
	
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	
	for (int i = 0; i < N; i++)
		A[i] = lower_bound(X.begin(), X.end(), A[i]) - X.begin() + 1;
	
	lint ori = 0;
	
	for (int i = 0; i < N; i++){
		ori += i - sum(A[i]);
		add(A[i]);
	}
	
	lint ans = ori + 1 - (X.size() != N);
	
	int hi = 0;
	vector<int> uCand, dCand, other, uA;
	bool checked[MAX_N];
	
	memset(checked, 0, sizeof(checked));
	
	for (int i = 0; i < N; i++){
		if (A[i] > hi){
			hi = A[i];
			uCand.push_back(i);
			uA.push_back(A[i]);
			checked[i] = true;
		}
	}
	
	int lo = 100001;
	for (int i = N - 1; i >= 0; i--){
		if (A[i] < lo && !checked[i]){
			lo = A[i];
			dCand.push_back(i);
			checked[i] = true;
		}
	}
	reverse(dCand.begin(), dCand.end());
	
	vector<pair<int, int> > tmp;
	vector<int> sorted;
	for (int i = 0; i < N; i++){
		if (!checked[i]){
			other.push_back(i);
			tmp.push_back(make_pair(A[i], i));
		}
	}
	
	sort(tmp.begin(), tmp.end());
	for (int i = 0; i < tmp.size(); i++) sorted.push_back(tmp[i].second);
	
	int ohead = 0, otail = 0;
	for (int i = 0; i < dCand.size(); i++){
		//?????????????????????
		while (otail < sorted.size() && A[sorted[otail]] < A[dCand[i]]){
			int p = upper_bound(uA.begin(), uA.end(), A[sorted[otail]]) - uA.begin();
			int q = upper_bound(uCand.begin(), uCand.end(), sorted[otail]) - uCand.begin();
			add(p, q, -1);
			if (p && A[uCand[p - 1]] == A[sorted[otail]]) p--; //???????????¨???????????£????????????????????¨???+2 ??????????????? +1
			add(p, q, -1);
			otail++;
		}
		
		//????????????
		while (ohead < other.size() && other[ohead] < dCand[i]){
			int p = upper_bound(uA.begin(), uA.end(), A[other[ohead]]) - uA.begin();
			int q = upper_bound(uCand.begin(), uCand.end(), other[ohead]) - uCand.begin();
			add(p, q, +1);
			if (p && A[uCand[p - 1]] == A[other[ohead]]) p--; //???????????¨???????????£????????????????????¨???+2 ??????????????? +1
			add(p, q, +1);
			ohead++;
		}
		
		//?????????????????????, ??????????????¨??? (????????¢????????????) * 2 ?????????????????????. +2 ??????????????? +1.
		int it = 0;
		while (otail + it < sorted.size() && A[sorted[otail + it]] == A[dCand[i]]){
			int p = lower_bound(uA.begin(), uA.end(), A[sorted[otail]]) - uA.begin();	// ???????????????????¨??????????NG
			int q = upper_bound(uCand.begin(), uCand.end(), sorted[otail + it++]) - uCand.begin();
			add(p, q, -1);
		}
		
		int p = upper_bound(uA.begin(), uA.end(), A[dCand[i]]) - uA.begin();
		int q = upper_bound(uCand.begin(), uCand.end(), dCand[i]) - uCand.begin();
		//???????????´??°
		if (p < q)
			ans = min(ans, ori - 1 - (segMax[0] + segAdd[0]));
		
		//????????????????????? (??????)
		while (otail < sorted.size() && A[sorted[otail]] == A[dCand[i]]){
			int p = upper_bound(uA.begin(), uA.end(), A[sorted[otail]]) - uA.begin();
			int q = upper_bound(uCand.begin(), uCand.end(), sorted[otail++]) - uCand.begin();
			add(p, q, -1); //?????§1 ???????????????????????§.
		}
	}
	printf("%lld\n", ans);
	
	return (0);
}

Measured memory_bytes: 6768