#include <bits/stdc++.h>
#define ll long long
#define ld double
#define pb push_back
#define pf push_front
#define ins insert
#define fr first
#define sc second
#define endl "\n"
#define ar array
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
void start(){ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);}
const ll inf = 1e12;
const ll mod = 1e9 + 7;
const ll N = 5e3 + 8;
struct seg{
ll t[N * 4];
void upd(ll v, ll tl, ll tr, ll pos, ll val){
if(tl > pos || tr < pos) return;
if(tl == tr){
t[v] = val;
return;
}
ll tm = (tl + tr) / 2;
upd(v * 2, tl, tm, pos, val);
upd(v * 2 + 1, tm + 1, tr, pos, val);
t[v] = t[v * 2] + t[v * 2 + 1];
}
void upd(ll pos, ll val){
upd(1, 1, N - 1, pos, val);
}
ll get(ll v, ll tl, ll tr, ll l, ll r){
if(tl > r || tr < l) return 0;
if(l <= tl && tr <= r) return t[v];
ll tm = (tl + tr) / 2;
return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm + 1, tr, l, r);
}
ll get(ll l, ll r){
return get(1, 1, N - 1, l, r);
}
}t;
ll dp[N];
ll id[N][N];
void solve() {
ll i, j;
ll n;
cin>>n;
ll a[n + 1];
ll pos[n + 1];
for(i=1;i<=n;i++) {
cin>>a[i];
pos[a[i]] = i;
}
for(i=0;i<n;i++){
ll c = 0;
for(j=1;j<=n;j++){
if(a[j] > i) {
id[i][a[j]] = c++;
}
}
}
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for(i=0;i<n;i++){
ll sum = 0;
for(j=i + 1;j<=n;j++){
sum += id[i][j];
t.upd(pos[j], 1);
sum -= t.get(pos[j] + 1, n);
dp[j] = min(dp[j], dp[i] + sum);
}
for(j=1;j<N * 4;j++) t.t[j] = 0;
}
cout<<dp[n]<<endl;
}
signed main(){
start();
ll t = 1;
//cin>>t;
while(t--) solve();
}
/*
12 1
))())((()(()
My answer
3
Correct answer
((()(()))())
1 8
4
*/
