#include<bits/stdc++.h> using namespace std; using i64 = long long; template <class T> struct fenwick{ int n; vector<T> tree; fenwick(int _n){ n = _n; tree = vector<T>(n); } void update(int i,T v){ for(;i < n;i |= (i + 1)){ tree[i] += v; } } T query(int i){ T ans = 0; for(;i >= 0;i = (i & (i + 1)) - 1){ ans += tree[i]; } return ans; } }; 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; fenwick<int> fen(n + 1); for(int j = n - 1;j >= 0;j--){ if(ta[j] == -1) continue; int wh = nhs[ta[j]]; int ex = fen.query(ta[j]); // int ex = distance(st.begin(),st.upper_bound(ta[j])); f[i][ta[j]] = -ex + wh - i; // st.insert(ta[j]); fen.update(ta[j],1); } } 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; }