#include<bits/stdc++.h> using namespace std; using i64 = long long; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<int> hs(n + 1); vector<int> a(n); for(int i = 0;i < n;i++){ int x; cin >> x; a[i] = x; hs[x] = i + 1; } vector<vector<int>> f(n + 1,vector<int>(n + 1)); for(int i = 1;i <= n;i++){ vector<int> ta(n,-1); int cnt = 0; for(int j = n - 1;j >= 0;j--){ if(a[j] <= i - 1){ cnt ++; }else{ assert(ta[j + cnt] == -1); ta[j + cnt] = a[j]; } } vector<int> nhs(n + 1); for(int i = 0;i < n;i++){ if(ta[i] != -1) nhs[ta[i]] = i + 1; } for(int j = i;j <= n;j++){ int wh = nhs[j]; int ex = 0; for(int k = nhs[j] + 1;k <= n;k++){ if(ta[k - 1] != -1 && ta[k - 1] >= i && ta[k - 1] <= j - 1) ex ++; } f[i][j] = -ex + wh - i; } } const i64 inf = 1e18; vector<i64> dp(n + 2,inf); dp[n + 1] = 0; for(int i = n;i >= 1;i--){ i64 tot = 0; for(int j = i;j <= n;j++){ tot += f[i][j]; dp[i] = min(dp[j + 1] + tot,dp[i]); } } cout << dp[1] << '\n'; return 0; }