#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
#define int ll
using namespace std;
const int N = 5e3 + 3,inf = 1e18;
int a[N],dp[N],id[N],val[N],pr[N];
int fen[N],D[N][N];
void upd(int idx,int dl){
while (idx <= 5000){
fen[idx] += dl;
idx += (idx & (-idx));
}
}
int get(int idx){
int s=0;
while (idx>0){
s += fen[idx];
idx -= (idx & (-idx));
}
return s;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n;
cin>>n;
for (int i = 1; i <= n; i++)
cin >> a[i],dp[i] = inf,id[a[i]] = i;
for (int i = 1; i <= n; i++){
int s = 0;
for (int l = i; l >= 1; l--){
upd(id[l],1);
s += (i - l + 1) - get(id[l]);
D[l][i] = s;
}
for (int l = i; l >= 1; l--)
upd(id[l],-1);
int c=0;
for (int j = 1; j <= n; j++){
if (a[j] > i) ++c;
val[j] = c;
}
for (int j = 1; j <= n; j++){
pr[j] = pr[j - 1] + val[id[j]];
}
for (int j = 1; j <= i; j++){
dp[i] = min(dp[i],dp[i - j] + pr[i] - pr[i - j] + D[i - j + 1][i]);
}
}
cout<<dp[n];
}
