#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define ll long long #define pb push_back #define vi vector<ll> #define f(i,a,b) for(ll i=a;i<b;i++) #define fr(i,a,b) for(ll i=a;i>=b;i--) #define fa(e,l) for(auto e:l) #define all(arr) arr.begin(),arr.end() #define pii pair<ll,ll> #define tii tuple<ll,ll,ll> #define coutpii(x) fa(e,x){cout<<e.first<<","<<e.second<<"\n";}cout<<"\n" #define couttup(x) fa(e,x){ll A,B,C,D,F;tie(A,B,C,D,F)=e;cout<<A<<","<<B<<","<<C<<","<<D<<","<<F<<"\n";}cout<<"\n" #define coutll(x) fa(e,x){cout<<e<<" ";}cout<<"\n" #define ordered_set tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> #define vvi vector<vi> #define v(a) vector<a> ll func(ll a,ll b){return a+b;} pair<vi,ll> seg(vi& arr,ll iv){ ll n=arr.size(),d=0; while((1LL<<d)<n)d++; ll n1=1LL<<d; vi t(2*n1,iv); f(i,0,n)t[n1+i]=arr[i]; fr(i,n1-1,1)t[i]=func(t[i*2],t[i*2+1]); return {t,n1}; } void update(vi& t,ll x,ll v,ll n1){ x+=n1; t[x]=v; x/=2; while(x>0){ t[x]=func(t[x*2],t[x*2+1]); x/=2; } } ll sum(ll l,ll r,vi& t,ll n1){ l+=n1;r+=n1; ll a=0; while(l<=r){ if(l%2==1){a=func(a,t[l]);l++;} if(r%2==0){a=func(a,t[r]);r--;} l/=2;r/=2; } return a; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n;cin>>n; vi h(n+1),p(n+1); f(i,1,n+1){cin>>h[i];p[h[i]]=i;} ll m=n+2; vi z(m,0),t1;ll n1; tie(t1,n1)=seg(z,0); const ll INF=(1LL<<62); vi dp(n+1,INF); dp[0]=0; vi tp,tb,cp(m,0),cb(m,0); f(i,1,n+1){ fill(all(cp),0); fill(all(cb),0); fill(all(z),0); f(vv,1,i){z[p[vv]]=1;cp[p[vv]]=1;} tie(tp,n1)=seg(z,0); fill(all(z),0); z[p[i]]=1;cb[p[i]]=1; tie(tb,n1)=seg(z,0); ll ic=0; ll ci=(i-1)-sum(1,p[i],tp,n1); ll bst=INF; for(ll l=i;l>=1;l--){ bst=min(bst,dp[l-1]+ic+ci); if(l==1)break; ll vv=l-1; ll A=sum(1,p[vv]-1,tb,n1); cp[p[vv]]--; update(tp,p[vv],cp[p[vv]],n1); ll ps=vv-1; ll B=ps-sum(1,p[vv],tp,n1); ci=ci-A+B; ll os=i-l+1; ll ge=os-sum(1,p[vv],tb,n1); ic+=ge; cb[p[vv]]++; update(tb,p[vv],cb[p[vv]],n1); // if(i==9&&l==4)cout<<ic<<" "<<ci<<"\n"; // cout<<i<<" "<<l<<" "<<bst<<"\n"; } dp[i]=bst; // cout<<i<<" "<<dp[i]<<"\n"; } cout<<dp[n]<<"\n"; }