#include <bits/stdc++.h> using namespace std; #define int long long #define pb(x) push_back(x) #define pp pop_back() struct node { node *left, *right; int S, E, M, val; node (int _s, int _e): S(_s), E(_e) { if (S==E) { val=0; return; } M=(S+E)/2; left=new node(S, M); right=new node(M+1, E); val=0; } void upd (int p, int v) { if (S==E) { val=v; return; } if (p<=M) left->upd(p, v); else right->upd(p, v); val=left->val+right->val; } int qry (int l, int r) { if (E<l || r<S) return 0; if (l<=S && E<=r) return val; return left->qry(l, r)+right->qry(l, r); } }*root, *root2; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int h[n], dis[n+1], dp[n+1]; dp[0]=0; for (int i=0; i<n; i++) { cin >> h[i]; dis[h[i]]=i; } dis[0]=0; root=new node(0, n-1); for (int i=1; i<=n; i++) dp[i]=INT_MAX; for (int i=0; i<n; i++) { //dp[i] stores the minimum value for a prefix of staircases ending at i root2=new node(0, n-1); //we use dp[i] to induct to dp[j] where j>i int cur=dp[i]; for (int j=i+1; j<=n; j++) { cur+=dis[j]-root->qry(0, dis[j])-root2->qry(dis[j], n-1); dp[j]=min(dp[j], cur); //cout << i << " " << j << " " << root->qry(0, dis[j]) << " " << root2->qry(dis[j], n-1) << "\n"; root2->upd(dis[j], 1); } root->upd(dis[i+1], 1); } cout << dp[n] << "\n"; return 0; }