#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(), (x).end()
typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;
const int mod = 1e9 + 7;
const int inf = INTMAX_MAX;
const bool tc = false;
int n; const int mxn = 5003;
int dp[mxn], a[mxn], pos[mxn + 1];
class Fenwick {
int n;
vector<int> bit1, bit2;
void add(vector<int>& bit, int idx, int val) {
for (; idx <= n; idx += idx & -idx)
bit[idx] += val;
}
int sum(const vector<int>& bit, int idx) const {
int s = 0;
for (; idx > 0; idx -= idx & -idx)
s += bit[idx];
return s;
}
int prefix_sum_1based(int idx) const {
return sum(bit1, idx) * idx - sum(bit2, idx);
}
public:
Fenwick(int n) : n(n), bit1(n + 1, 0), bit2(n + 1, 0) {}
// add val to range [l, r] where l, r are 0-based inclusive
void range_add(int l, int r, int val) {
// convert to 1-based
int L = l + 1;
int R = r + 1;
add(bit1, L, val);
if (R + 1 <= n) add(bit1, R + 1, -val);
add(bit2, L, val * (L - 1));
if (R + 1 <= n) add(bit2, R + 1, -val * R);
}
// sum of range [l, r] where l, r are 0-based inclusive
int range_sum(int l, int r) const {
int L = l + 1;
int R = r + 1;
return prefix_sum_1based(R) - prefix_sum_1based(L - 1);
}
};
// int cost(int x, int y) {
// // x < y
// // add from x + 1 to y, pos[i] - cntbefore[1,x]
// bool dbg = false;
// // if (x == 0 && y == 3) dbg = true;
// if (max(x, y) > n) return (int)0;
// int ans = 0;
// for (int i = x + 1; i <= y; i++) {
// int bfr = 0;
// for (int j = 0; j < pos[i]; j++) if (a[j] <= x || (a[j] > i && a[j] <= y)) bfr++;
// // for (int j = 1; j <= x; j++) if (pos[j] < pos[i]) bfr++;
// if (dbg) cout << i << " is i and " << pos[i] << " " << bfr << '\n';
// ans += pos[i] - bfr;
// }
// if (dbg) cout << ans << " ans\n";
// return ans;
// }
inline void solve() {
cin >> n; for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) {pos[a[i]] = i; dp[i] = 1e18; dp[i + 1] = 1e18;}
dp[1] = pos[1]; dp[0] = 0;
for (int i = 2; i <= n; i++) {
Fenwick ft(n + 1); vi cost1(n + 1); // how many from [i + 1, n] appear before i
for (int j = i + 1; j <= n; j++) {ft.range_add(pos[j], pos[j], 1);}
for (int j = 0; j <= n; j++) cost1[j] = ft.range_sum(0, pos[j] - 1);
Fenwick ft2(n + 1); vi cost2(n + 1);
for (int j = i; j >=0; j--) {
cost2[j] = ft2.range_sum(pos[j] + 1, n);
ft2.range_add(pos[j], pos[j], 1);
}
// cout << i << " i\n";
// cout << "cost1:\n";
// for (int i = 1; i <= n; i++) cout << cost1[i] << " ";
// cout << '\n';
// cout << "cost2:\n";
// for (int i = 1; i <= n; i++) cout << cost2[i] << " ";
// cout << '\n';
int cost = cost1[i] + cost2[i];
for (int j = i - 1; j >= 0; j--) {
dp[i] = min(dp[i], dp[j] + cost);
// cout << j << " -> " << i << "\n";
// cout << "dpj " << dp[j] << " cost1,2 " << cost1[j] << " " << cost2[j] << " curcost " << cost << '\n';
// cout << "so cost is " << dp[j] + cost << '\n';
cost += cost1[j] + cost2[j];
}
// cout << dp[i] << " final\n";
}
cout << dp[n] << '\n';
}
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
signed main() {
ios::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
//setIO();
int t = 1;
if (tc) {
cin >> t;
}
while (t--) {
solve();
}
}
