#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
const int M=2e5+10;
int ti=0,h[N],p[N],rt[N],n,dp[2][N],mn[N];
struct node{
int l,r,val;
}s[M];
int cp(int x){s[++ti]=s[x]; return ti;}
void build(int l,int r,int idx){
ti=max(ti,idx);
if(l==r){
s[idx]={0,0,0};
return;
}
int m=(l+r)/2;
build(l,m,idx*2);
build(m+1,r,idx*2+1);
s[idx].l=idx*2,s[idx].r=idx*2+1;
s[idx].val=s[s[idx].l].val+s[s[idx].r].val;
}
int update(int l,int r,int idx,int a){
if(a<l || a>r) return idx;
int u=cp(idx);
if(l==r){
s[u].val++;
return u;
}
int m=(l+r)/2;
if(a<=m) s[u].l=update(l,m,s[idx].l,a);
else s[u].r=update(m+1,r,s[idx].r,a);
s[u].val=s[s[u].l].val+s[s[u].r].val;
return u;
}
int query(int l,int r,int idx,int a,int b){
if(a>r || b<l) return 0;
if(a<=l && b>=r) return s[idx].val;
int m=(l+r)/2;
return query(l,m,s[idx].l,a,b)+query(m+1,r,s[idx].r,a,b);
}
int ask(int l,int r,int vl,int vr){
if(l>r) return 0;
return query(1,n,rt[vr],l,r)-query(1,n,rt[vl-1],l,r);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>h[i],p[h[i]]=i;
build(1,n,1);
rt[0]=1;
for(int i=1;i<=n;i++){
rt[i]=update(1,n,rt[i-1],p[i]);
}
for(int i=1;i<=n;i++) dp[n&1][i]=1e9;
dp[n&1][n]=ask(p[n]+1,n,1,n);
//cout<<dp[n][n] <<"\n";
mn[n]=dp[n&1][n];
for(int i=n-1;i>=1;i--){
int now=i&1;
int pre=(i+1)&1;
for(int j=1;j<=n;j++) dp[now][j]=1e9;
mn[i]=1e9;
dp[now][i]=mn[i+1]+ask(p[i],n,1,i-1);
mn[i]=min(mn[i],dp[now][i]);
for(int j=i+1;j<=n;j++){
int add=0,del=0;
del=ask(1,p[i],i+1,j);
add=ask(p[i]+1,n,1,j);
dp[now][j]=dp[pre][j]+add-del;
mn[i]=min(mn[i],dp[now][j]);
}
// for(int j=i;j<=n;j++){
// cout<<i <<" " <<j <<" " <<dp[now][j] <<"\n";
// }
}
cout<<mn[1];
}
