#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 5e3 + 7;
const ll inf = 1e18 + 7;
int n, a[mxN], vt[mxN];
ll dp[mxN];
struct Segment
{
int node[mxN * 4];
void Reset(int j = 1, int l = 1, int r = n)
{
node[j] = 0;
if (l == r)
return;
int mid = (l + r) / 2;
Reset(j * 2, l, mid);
Reset(j * 2 + 1, mid + 1, r);
}
void Upd(int vt, int j = 1, int l = 1, int r = n)
{
if (l > vt || vt > r)
return;
node[j]++;
if (l == r)
return;
int mid = (l + r) / 2;
Upd(vt, j * 2, l, mid);
Upd(vt, j * 2 + 1, mid + 1, r);
}
int Get(int u, int v, int j = 1, int l = 1, int r = n)
{
if (u > r || l > v)
return 0;
if (u <= l && r <= v)
return node[j];
int mid = (l + r) / 2;
return Get(u, v, j * 2, l, mid) + Get(u, v, j * 2 + 1, mid + 1, r);
}
};
Segment tree[2];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen(task".INP", "r", stdin);
//freopen(task".OUT", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
vt[a[i]] = i;
dp[i] = inf;
}
for (int i = n; i >= 1; i--)
{
tree[1].Reset();
ll cost = 0;
for (int j = i; j >= 1; j--)
{
cost += n - vt[j] - tree[0].Get(vt[j] + 1, n);
cost -= tree[1].Get(1, vt[j]);
tree[1].Upd(vt[j]);
dp[j] = min(dp[j], dp[i + 1] + cost);
}
tree[0].Upd(vt[i]);
}
cout << dp[1];
}
