#include <bits/stdc++.h> using namespace std; #define int long long #define pb(x) push_back(x) #define pp pop_back() 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; int a[n+1], dolphyisgay[n+1]; memset(a, 0, sizeof(a)); for (int i=1; i<=n; i++) dp[i]=INT_MAX; for (int i=0; i<n; i++) { dolphyisgay[i]=0; for (int j=i+1; j<n; j++) if (h[i]>h[j]) dolphyisgay[i]++; } for (int i=0; i<n; i++) { //dp[i] stores the minimum value for a prefix of staircases ending at i //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]-2*a[dis[j]]+a[n-1]-dolphyisgay[dis[j]]; dp[j]=min(dp[j], cur); //cout << i << " " << j << " " << a[dis[j]] << " " << root->qry(dis[j], n-1) << "\n"; } for (int j=dis[i+1]; j<=n; j++) a[j]++; } cout << dp[n] << "\n"; return 0; }