#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 j = 0;j < n;j++){ if(ta[j] != -1) nhs[ta[j]] = j + 1; } set<int> st; for(int j = n - 1;j >= 0;j--){ if(ta[j] == -1) continue; int wh = nhs[ta[j]]; int ex = distance(st.begin(),st.upper_bound(ta[j])); f[i][ta[j]] = -ex + wh - i; st.insert(ta[j]); } } 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; }