#include <bits/stdc++.h> using namespace std; #define ll long long #define fr(i,a,b,c) for(int i = a;i<b;i+=c) #define fre(i,a,b,c) for(int i = a;i>=b;i-=c) #define fs first #define sc second #define all(a) a.begin(),a.end() #define IINF 2000000005 #define LINF 1000000000000000005 #define MOD 1000000007 #define str string #define endl '\n' using pii = pair<int,int>; using pll = pair<ll,ll>; using tiii = tuple<int,int,int>; struct FT{ int n; vector<int> bit; void add(int v,int id){ for(;id <= n;id += id & -id)bit[id] += v; } int query(int id){ int v = 0; for(;id > 0;id -= id & -id)v += bit[id]; return v; } FT(int n){ bit.resize(n+1); this->n = n; } int qu(int l,int r){ return query(r) - query(l-1); } void clear(){ fr(i,1,n+1,1)bit[i] = 0; } }; int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); int n;cin >> n; vector<int> a(n); fr(i,0,n,1)cin >> a[i]; vector<vector<int>> pf(n+1,vector<int>(n+1)); FT tree(n); fr(i,0,n,1){ fr(j,a[i],n+1,1){ pf[j][a[i]] += tree.qu(j + 1,n); } tree.add(1,a[i]); } tree.clear(); fre(i,n-1,0,1){ fr(j,a[i],n+1,1){ pf[j][a[i]] += tree.qu(a[i],j); } tree.add(1,a[i]); } fr(i,1,n+1,1){ fre(j,i-1,1,1)pf[i][j] += pf[i][j+1]; } vector<int> dp(n+1,IINF); dp[0] = 0; fr(i,1,n+1,1){ fr(j,1,i+1,1){ dp[i] = min(dp[i],dp[j-1] + pf[i][j]); } } cout << dp[n] << endl; }