// Tanawin Thongbai
#include <bits/extc++.h>
using namespace std;
class Segm_Elem {
public:
bool is_real, is_added;
int sum, unreal, cnt;
Segm_Elem() {
is_real = false;
is_added = false;
sum = 0;
unreal = 0;
cnt = 0;
}
Segm_Elem(int sum, int unreal, int cnt, bool is_real) {
this -> is_real = is_real;
this -> is_added = true;
this -> sum = sum;
this -> unreal = unreal;
this -> cnt = cnt;
}
};
const int N = 5000;
int orig[N + 1], indices[N + 1], dp_L[N + 1][N + 1], dp[N + 1];
Segm_Elem segm_merge(const Segm_Elem &a, const Segm_Elem &b) {
if(!a.is_added) {
return b;
}
if(!b.is_added) {
return a;
}
if(!a.is_real) {
if(b.is_real) {
return Segm_Elem(b.sum, a.unreal + b.unreal, b.cnt, true);
}
return Segm_Elem(0, a.unreal + b.unreal, 0, false);
}
return Segm_Elem(a.sum + b.sum + a.cnt * b.unreal, a.unreal + b.unreal, a.cnt + b.cnt, true);
}
void segm_update(Segm_Elem *const &segm, const int &clogn, int index, Segm_Elem tr) {
index += (1 << clogn);
segm[index] = tr;
for(int i = index / 2; i >= 1; i /= 2) {
segm[i] = segm_merge(segm[i * 2], segm[i * 2 + 1]);
}
}
Segm_Elem segm_query(Segm_Elem *const &segm, const int &clogn, int st, int ed) {
int l = st + (1 << clogn);
int r = ed + (1 << clogn);
queue<Segm_Elem> l_part = queue<Segm_Elem>();
stack<Segm_Elem> r_part = stack<Segm_Elem>();
while(l <= r) {
if(l % 2 == 1) {
l_part.push(segm[l++]);
}
if(r % 2 == 0) {
r_part.push(segm[r--]);
}
l /= 2;
r /= 2;
}
bool first_time = true;
Segm_Elem ans;
while(!l_part.empty()) {
Segm_Elem s = l_part.front();
l_part.pop();
if(first_time) {
first_time = false;
ans = s;
} else {
ans = segm_merge(ans, s);
}
}
while(!r_part.empty()) {
Segm_Elem s = r_part.top();
r_part.pop();
if(first_time) {
first_time = false;
ans = s;
} else {
ans = segm_merge(ans, s);
}
}
return ans;
}
void fenw_update(int *const fenw, const int &n, int i, int x) {
for(; i <= n; i += i & -i) {
fenw[i] += x;
}
}
int fenw_query(int *const fenw, const int &n, int i) {
int ans = 0;
for(; i >= 1; i -= i & -i) {
ans += fenw[i];
}
return ans;
}
int main() {
int n_elem;
scanf("%d", &n_elem);
for(int i = 1; i <= n_elem; ++i) {
scanf("%d", &orig[i]);
indices[orig[i]] = i;
}
for(int i = 1; i <= n_elem - 1; ++i) {
dp_L[i][i] = 0;
int *fenw = new int[n_elem + 1]{};
int k = 1e9;
for(int j = i + 1; j <= n_elem; ++j) {
fenw_update(fenw, n_elem, n_elem - indices[j - 1] + 1, 1);
int mv = 0;
if(k > indices[j - 1]) {
k = indices[j - 1];
}
if(k != 1e9 && k < indices[j]) {
mv = fenw_query(fenw, n_elem, n_elem - k + 1) - fenw_query(fenw, n_elem, n_elem - indices[j]);
}
dp_L[i][j] = mv + dp_L[i][j - 1];
}
delete[] fenw;
}
int clogn = (int)ceil(log2(n_elem));
Segm_Elem *segm = new Segm_Elem[1 << (clogn + 1)]{};
for(int i = 1; i <= n_elem; ++i) {
deque<int> deq = deque<int>();
for(int j = 1; j <= n_elem; ++j) {
if(i >= orig[n_elem - j + 1]) {
segm_update(segm, clogn, j - 1, Segm_Elem(0, 1, 0, false));
}
if(orig[j] > i) {
continue;
}
if(deq.empty() || orig[deq.back()] < orig[j]) {
deq.push_back(j);
}
}
int mn = 1e9;
for(int j = 0; j <= i - 1; ++j) {
while(!deq.empty() && orig[deq.front()] <= j) {
deq.pop_front();
}
if(j > 0) {
segm_update(segm, clogn, n_elem - indices[j], Segm_Elem(0, 0, 1, true));
}
int mv = 0;
if(j > 0 && !deq.empty()) {
int k = deq.front();
Segm_Elem ans = segm_query(segm, clogn, 0, n_elem - k);
int x = ans.sum;
mv = x;
}
mn = min(mn, dp[j] + dp_L[j + 1][i] + mv);
}
dp[i] = mn;
for(int j = 1; j <= n_elem; ++j) {
if(i >= orig[n_elem - j + 1]) {
segm_update(segm, clogn, j - 1, Segm_Elem());
}
}
}
printf("%d\n", dp[n_elem]);
return 0;
}
