#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for(int i = a ; i <= b ; i++)
#define FORD(i, a, b) for(int i = a ; i >= b ; i--)
#define REP(i, a, b) for(int i = a ; i < b ; i++)
const bool Multitest = 0, Local = 0;
const int N = 5005;
int n, a[N], pos[N];
namespace sub1
{
vector<int> v; int b[N];
int check()
{
int cnt = 0;
REP(i, 0, v.size())
{
if(i + 1 < v.size() && v[i] >= v[i + 1] + 2)
{
return 1e9;
}
}
// REP(i, 0, v.size()) cout << v[i] << ' '; cout << '\n';
REP(i, 0, v.size())
{
b[i] = pos[v[i]];
}
REP(i, 0, v.size())
{
REP(j, i + 1, v.size())
{
if(b[i] > b[j]) cnt++;
}
}
return cnt;
}
void solve()
{
for(int i = 0 ; i < n ; i++) v.push_back(i + 1);
int ans = 1e9;
do
{
ans = min(ans, check());
} while(next_permutation(v.begin(), v.end()));
cout << ans;
}
}
namespace sub234
{
const int Sub = 805;
int dp[Sub], cost[Sub][Sub], val[Sub][Sub], b[Sub];
int get(int p1, int p2)
{
int cnt = 0;
FOR(i, 1, p1)
{
if(b[i] > b[p2]) cnt++;
}
return cnt;
}
void solve()
{
for(int i = 1 ; i <= n ; i++) b[i] = pos[i];
for(int j = 1 ; j <= n ; j++)
{
for(int i = j ; i >= 1 ; i--)
{
val[i][j] = val[i + 1][j] + (b[i] < b[j]);
}
}
for(int i = 1 ; i <= n ; i++)
{
for(int j = i ; j <= n ; j++)
{
cost[i][j] = cost[i][j - 1] + get(i - 1, j) + val[i][j];
}
}
// cerr << val[1][2] << '\n';
for(int i = 1 ; i <= n ; i++)
{
dp[i] = 1e9;
for(int j = 1 ; j <= i ; j++)
{
dp[i] = min(dp[i], dp[j - 1] + cost[j][i]);
}
}
cout << dp[n];
}
}
namespace sub5
{
const int Sub = 5005;
int dp[Sub], cost[Sub][Sub], val[Sub][Sub], b[Sub], f[Sub], g[Sub][Sub];
void solve()
{
for(int i = 1 ; i <= n ; i++) b[i] = pos[i];
for(int j = 1 ; j <= n ; j++)
{
for(int i = j ; i >= 1 ; i--)
{
val[i][j] = val[i + 1][j] + (b[i] < b[j]);
}
}
for(int i = 1 ; i <= n ; i++)
{
for(int j = i ; j <= n ; j++)
{
g[i - 1][j] = f[n] - f[b[j]];
}
for(int x = b[i] ; x <= n ; x++) f[x]++;
}
for(int i = 1 ; i <= n ; i++)
{
for(int j = i ; j <= n ; j++)
{
cost[i][j] = cost[i][j - 1] + g[i - 1][j] + val[i][j];
}
}
// cerr << val[1][2] << '\n';
for(int i = 1 ; i <= n ; i++)
{
dp[i] = 1e9;
for(int j = 1 ; j <= i ; j++)
{
dp[i] = min(dp[i], dp[j - 1] + cost[j][i]);
}
}
cout << dp[n];
}
}
void work()
{
cin >> n;
FOR(i, 1, n) cin >> a[i], pos[a[i]] = i;
sub5::solve();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int q = 1;
if(Local && fopen("code.inp", "r"))
{
freopen("code.inp", "r", stdin);
freopen("code.ans", "w", stdout);
}
if(Multitest) cin >> q;
while(q--) work();
}
