#include <iostream> using namespace std; const int N = 5005; int dp[N], inv[N][N], ext[N][N], ind[N], ft[2][N]; void Add(int t, int i){ for (; i; i -= i & -i) ft[t][i]++; } int get(int t, int i, int ans = 0){ for (; i < N; i += i & -i) ans += ft[t][i]; return ans; } int main(){ int n; cin>>n; for (int i=1, a;i<=n;i++) cin>>a, ind[a] = i, dp[i] = 1e9; for (int l=1;l<=n;l++){ for (int i=1;i<N;i++) ft[0][i] = 0; for (int r=l;r<=n;r++){ inv[l][r] = inv[l][r-1] + get(0, n - ind[r] + 1); ext[l][r] = ext[l][r-1] + get(1, ind[r]); Add(0, n - ind[r] + 1); } Add(1, ind[l]); } for (int i=0;i<n;i++){ for (int j=i+1;j<=n;j++) dp[j] = min(dp[j], dp[i] + inv[i+1][j] + ext[i+1][j]); } cout<<dp[n]<<'\n'; }