#include <bits/stdc++.h>
using namespace std;
const int MX=5005;
int N;
int H[MX], dp[MX], cnt[MX][MX], curCnt[MX], pos[MX], sum[MX][MX], diag[MX];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N;
for(int i=1;i<=N;i++) cin>>H[i];
for(int i=1;i<=N;i++) dp[i]=1e9;
for(int i=1;i<=N;i++) {
for(int j=H[i];j<=N;j++) curCnt[j]++;
for(int j=1;j<=N;j++) cnt[H[i]][j]=curCnt[j];
}
for(int j=1;j<=N;j++) {
for(int i=1;i<=N;i++) {
sum[i][j]+=sum[i-1][j];
sum[i][j]+=cnt[i][j];
}
}
for(int j=1;j<=N;j++) {
diag[j]+=diag[j-1];
diag[j]+=cnt[j][j-1];
}
for(int i=0;i<=N;i++) {
for(int k=i+1;k<=N;k++) {
int cost=0;
cost+=sum[k][N]-sum[i][N];
cost-=sum[k][k]-sum[i][k];
cost-=sum[k][i]-sum[i][i];
cost+=diag[k]-diag[i];
dp[k]=min(dp[k],dp[i]+cost);
}
}
cout<<dp[N]<<'\n';
}
