#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #include <bits/stdc++.h> using namespace std; #define int long long #define pll pair<long long, long long> #define mp make_pair #define pb push_back #define f first #define s second #define endl '\n' #define ld long double #define sz(x) static_cast<int>((x).size()) #define i5 tuple<int,int,int,int,int> #define all(x) x.begin(), x.end() #define iiii tuple<int, int,int,int> #define ld long double #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> const int maxn=5005; int fw[3][maxn]; void upd(int t, int x, int v){ while(x <= maxn){ fw[t][x]+=v; x+=(x&(-x)); } } int qry(int t, int x){ int ret=0; while(x > 0){ ret += fw[t][x]; x-=(x&(-x)); } return ret; } signed main(){ int n;cin>>n; vector<int> v(n+1), pos(n+1); for(int i=1;i<=n;i++){ cin>>v[i]; pos[v[i]]=i; } vector<vector<int>> cost(n+1, vector<int>(n+1, 0)); for(int i=1;i<=n;i++){ upd(1, i, 1); } /*cout<<pos[1]<<endl; cout<<qry(1, pos[1]-1); return 0;*/ vector<int> rb; for(int j=1;j<=n;j++){ for(auto it: rb){ upd(2, it, -1); } rb.clear(); int cc=0; for(int i=j;i<=n;i++){ int minus=qry(2, maxn) - qry(2, pos[i]); int mv=qry(1, pos[i]-1); cc += mv - minus; upd(2, pos[i], 1); rb.pb(pos[i]); cost[j][i] = cc; //printf("cost of %lld to %lld is %lld,mv %lld minused %lld\n", j, i, cc, mv, minus); } upd(1, pos[j], -1); //if(j==1)break; } vector<int> dp(n+1, 1e9); dp[0]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ dp[i]=min(dp[i], dp[j-1] + cost[j][i]); } } cout<<dp[n]; }