#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 5e3 + 5;
const int inf = 1e9;
int rev[maxn][maxn],inv[maxn][maxn],dp[maxn],a[maxn],pos[maxn],pre[maxn];
void prepare_rev(int n){
for (int i = 1 ; i < n ; i++)
for (int j = i + 1 ; j <= n ; j++)
if (a[i] < a[j])
rev[a[i]][a[j]]++;
for (int len = 3 ; len <= n ; len++)
for (int i = 1 ; i <= n - len + 1 ; i++){
int l = i,r = i + len - 1;
rev[l][r] += rev[l + 1][r] + rev[l][r - 1] - rev[l + 1][r - 1];
}
}
void prep_inv(int L,int n){
for (int i = n ; i > 0 ; i--)
pre[i] = pre[i + 1] + (a[i] < L);
int tmp = 0;
for (int R = L ; R <= n ; R++){
tmp += pre[pos[R]];
inv[L][R] += tmp;
}
}
void prepare_inv(int n){
for (int L = 1 ; L <= n ; L++){
for (int i = 1 ; i <= n ; i++) pre[i] = 0;
prep_inv(L,n);
}
}
void refresh(int n){
for (int i = 2 ; i <= n ; i++) dp[i] = inf;
}
int solve(int n){
for (int i = 1 ; i <= n ; i++){
for (int j = i ; j > 0 ; j--)
dp[i] = min(dp[i],dp[j - 1] + rev[j][i] + inv[j][i]);
}
return dp[n];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin >> n;
for (int i = 1 ; i <= n ; i++){
cin >> a[i];
pos[a[i]] = i;
}
prepare_rev(n);
prepare_inv(n);
refresh(n);
cout << solve(n);
return 0;
}
