#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ft first
#define sc second
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int, int>
#define vi vector<int>
#define tii tuple<int, int, int>
#define tiii tuple<int, int, int, int>
#define tiiii tuple<int, int, int, int, int>
#define vpi vector<pi>
#define vtii vector<tii>
#define vtiii vector<tiii>
const int N = 5009, MOD = 1e9 + 7, INF = int(1e9);
int ile[N][N];
int p[N], poz[N];
void count_ile(int n){
for(int i = 1; i <= n; i++){
for(int j = i - 1; j > 0; j--){
ile[i][j] = ile[i][j + 1] + (poz[j] < poz[i]);
}
}
}
int inw[N][N];
void count_inw(int n){
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
inw[i][j] = inw[i][j - 1] + ile[j][i];
}
}
}
int ile_w[N][N];
void count_ile_w(int n){
for(int i = 1; i <= n; i++){
int akt = 0;
for(int j = 1; j <= n; j++){
ile_w[i][j] = akt;
akt += (p[j] > i);
}
}
}
int s[N][N];
void count_s(int n){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
s[i][j] = s[i][j - 1] + ile_w[i][poz[j]];
}
}
}
int v[N][N];
void count_v(int n){
count_ile(n);
count_ile_w(n);
count_s(n);
count_inw(n);
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
v[i][j] = inw[i][j] + s[j][j] - s[j][i - 1];
}
}
}
int dp[N][N];
void count_dp(int n){
count_v(n);
for(int i = 1; i <= n; i++){
int x = INF;
for(int j = i - 1; j > 0; j--) x = min(x, dp[j][i - j]);
if(x == INF) x = 0;
for(int j = 1; j <= (n - i + 1); j++){
dp[i][j] = v[i][i + j - 1] + x;
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
// random_device rd;
// mt19937_64 gen(rd());
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> p[i];
poz[p[i]] = i;
}
count_dp(n);
int ans = INF;
for(int i = 1; i <= n; i++) ans = min(ans, dp[i][n - i + 1]);
cout << ans << "\n";
return 0;
}
