#include<bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 5005
#define LOG 17
using namespace std;
// da xem hint
// toi nhan xet duoc: day se co dang: 1 2 3 7 6 5 4 8 10 9... tuc la 1 doan giam, roi nhay len
// hint mau chot:
bool ghuy4g;
const ll inf = 1e9;
ll n, a[N], idx[N], b[N][N], pf[N][N];
ll cost[N][N];
ll bit[N];
void upd(ll u, ll v) {
ll idx = u;
while (idx <= n) {
bit[idx] += v;
idx += idx & (-idx);
}
}
ll get(ll u) {
ll idx = u, ans = 0;
while (idx > 0) {
ans += bit[idx];
idx -= idx & (-idx);
}
return ans;
}
ll dp[N];
void solve() {
for (int i = 1; i <= n; i ++) {
dp[i] = inf;
for (int j = i; j >= 1; j --) {
dp[i] = min(dp[i], dp[j - 1] + cost[j][i]);
}
}
cout << dp[n];
}
void pre() {
for (int i = n; i >= 1; i --) {
for (int j = 1; j <= n; j ++) {
b[i][j] = b[i + 1][j];
}
b[i][idx[i]] ++ ;
for (int j = 1; j <= n; j ++) {
pf[i][j] = pf[i][j - 1] + b[i][j];
}
}
for (int r = 1; r <= n; r ++) {
for (int i = 1; i <= n; i ++) {
bit[i] = 0;
}
ll base = 0, sum = 0, base2 = 0;
for (int l = r; l >= 1; l --) {
base = base + sum - get(idx[l]);
base2 = base2 + pf[r + 1][idx[l] - 1]; // -1 hay ko cung duoc
cost[l][r] = base + base2;
//cout << l << " " << r << " " << cost[l][r] << endl;
upd(idx[l], 1);
sum ++ ;
}
}
}
bool klinh;
signed main() {
//freopen("mario.inp", "r", stdin);
//freopen("mario.out", "w", stdout);
//srand(time(0));
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
idx[a[i]] = i;
}
pre();
solve();
cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
//cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";//
}
