#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[5005];
int pre[5005][5005];
int cost[5005][5005];
int pos[5005];
int dp[5005];
int inf=1e15;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],pre[a[i]][i]++,pos[a[i]]=i;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)pre[i][j]=pre[i][j]+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
/*for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cerr<<pre[i][j]<<" ";
}
cerr<<"\n";
}*/
for(int i=n;i>=1;i--)for(int j=i;j<=n;j++){
cost[i][j]=cost[i+1][j];
//inv >j , i
cost[i][j]+=pre[n][pos[i]-1]-pre[j][pos[i]-1];
if(i!=j){
//inv i, >i & <=j
cost[i][j]+=pre[j][n]-pre[i][n]-pre[j][pos[i]]+pre[i][pos[i]];
}
}
/*cerr<<"\n";
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cerr<<cost[i][j]<<" ";
}
cerr<<"\n";
}*/
for(int i=1;i<=n;i++)dp[i]=inf;
for(int i=1;i<=n;i++)for(int j=1;j<=i;j++){
dp[i]=min(dp[i],dp[j-1]+cost[j][i]);
}
/*cerr<<"\n";
for(int i=1;i<=n;i++)cerr<<dp[i]<<" ";
cerr<<"\n";*/
cout<<dp[n];
}
