#include "bits/stdc++.h" using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // https://codeforces.com/blog/entry/79148 class Timer: chrono::high_resolution_clock { const time_point start_time; public: Timer(): start_time(now()) {} rep elapsed_time() const { return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count(); } } timer; struct FenwickTree { int n; vector<int> tree; FenwickTree(int n_) { n = n_; tree.resize(n + 1, 0); } void update(int p, int k) { while (p <= n) { tree[p] += k; p += p & (-p); } } int prefixQuery(int r) { int res = 0; while (r) { res += tree[r]; r -= r & (-r); } return res; } int query(int l, int r) { return prefixQuery(r) - prefixQuery(l - 1); } }; int main() { cin.tie(0); ios::sync_with_stdio(0); int n; cin >> n; vector<int> pos(n + 1), dp(n + 1, 1e9); for (int i = 1; i <= n; i++) { int x; cin >> x; pos[x] = i; } vector<vector<int>> inv(n + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= n; i++) { FenwickTree fwt(n); for (int j = i; j <= n; j++) { inv[i][j] = inv[i][j - 1] + fwt.query(pos[j], n); fwt.update(pos[j], 1); } } dp[0] = 0; for (int i = 1; i <= n; i++) { FenwickTree fwt(n); for (int j = i; j <= n; j++) { fwt.update(pos[j], 1); } int cur = 0; for (int j = i; j <= n; j++) { cur += fwt.prefixQuery(pos[j]) - 1; dp[j] = min({dp[j], dp[i - 1] + cur, dp[i - 1] + cur - 2 * inv[i][j] + (j - i + 1) * (j - i) / 2}); fwt.update(pos[j], -1); } } cout << dp[n]; return 0; }