#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>> f1(n + 1,vector<int>(n + 1)); for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ for(int p = hs[j];p <= n;p++){ if(a[p - 1] < i) f1[j][i] ++; } } } vector<vector<vector<int>>> f2(n + 1,vector<vector<int>>(n + 1,vector<int>(n + 1))); for(int i = 1;i <= n;i++){ vector<int> te(n + 1); for(int j = i;j <= n;j++){ for(int k = hs[j];k >= 1;k--){ if(a[k - 1] >= i && a[k - 1] < j) te[a[k - 1]] ++; } for(int k = i;k <= j;k++){ f2[i][j][k] = te[k]; } } } const i64 inf = 1e18; vector<i64> dp(n + 2,inf); dp[n + 1] = 0; for(int i = n;i >= 1;i--){ for(int j = i;j <= n;j++){ i64 tot = 0; vector<int> nhs(n + 1); nhs = hs; for(int k = i;k <= j;k++){ int s = hs[k] + 1; nhs[k] += f1[k][i]; nhs[k] += f2[i][j][k]; } for(int k = i;k <= j;k++){ tot += abs(nhs[j - (k - i)] - k); } dp[i] = min(dp[j + 1] + tot,dp[i]); } } cout << dp[1] << '\n'; return 0; }