#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
// #include <sys/resource.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const bool debug = true;
#define ff first
#define ss second
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define YN(x) \
if (x) \
yes; \
else \
no;
#define all(X) (X).begin(), (X).end()
#define rall(X) (X).rbegin(), (X).rend()
#define UNIQUE(x) sort(all(x)), (x).erase(unique(all(x)), (x).end())
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
const int mod = 1e9 + 7;
#ifndef ONLINE_JUDGE
#define dbg(x) \
cerr << #x << " "; \
print(x); \
cerr << endl;
#else
#define dbg(x)
#endif
#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#define __builtin_popcountll __popcnt64
static inline int __builtin_clz(unsigned int x)
{
unsigned long leading_zero = 0;
if (_BitScanReverse(&leading_zero, x))
{
return 31 - leading_zero;
}
return 32;
}
static inline int __builtin_clzll(unsigned __int64 x)
{
unsigned long leading_zero = 0;
if (_BitScanReverse64(&leading_zero, x))
{
return 63 - leading_zero;
}
return 64;
}
#endif
// void increaseStack(rlim_t stackSize) {
// struct rlimit rl;
// int result;
//
// result = getrlimit(RLIMIT_STACK, &rl);
// if (result == 0) {
// if (rl.rlim_cur < stackSize) {
// rl.rlim_cur = stackSize;
// result = setrlimit(RLIMIT_STACK, &rl);
// if (result != 0) {
// cerr << "Error setting stack size." << endl;
// }
// }
// }
// }
struct Mint
{
static int m;
int v;
Mint(long long value = 0)
{
v = value % m;
if (v < 0)
v += m;
}
static void set_mod(int new_mod) { m = new_mod; }
friend istream &operator>>(istream &inp, Mint &a)
{
ll x;
inp >> x;
a = x;
return inp;
}
friend ostream &operator<<(ostream &out, const Mint &a)
{
out << a.v;
return out;
}
Mint &operator+=(const Mint &o)
{
v += o.v;
if (v >= m)
v -= m;
return *this;
}
Mint &operator-=(const Mint &o)
{
v -= o.v;
if (v < 0)
v += m;
return *this;
}
Mint &operator*=(const Mint &o)
{
v = (long long)v * o.v % m;
return *this;
}
Mint pow(long long b) const
{
Mint res = 1, a = *this;
while (b > 0)
{
if (b & 1)
res *= a;
a *= a;
b >>= 1;
}
return res;
}
Mint inv() const
{
return pow(m - 2);
}
Mint &operator++()
{
v++;
if (v == m)
v = 0;
return *this;
}
Mint &operator--()
{
if (v == 0)
v = m;
--v;
return *this;
}
Mint &operator/=(const Mint &other) { return *this *= other.inv(); }
friend Mint operator+(const Mint &a, const Mint &b) { return Mint(a) += b; }
friend Mint operator-(const Mint &a, const Mint &b) { return Mint(a) -= b; }
friend Mint operator*(const Mint &a, const Mint &b) { return Mint(a) *= b; }
friend Mint operator/(const Mint &a, const Mint &b) { return Mint(a) /= b; }
friend bool operator==(const Mint &a, const Mint &b) { return a.v == b.v; }
friend bool operator!=(const Mint &a, const Mint &b) { return a.v != b.v; }
Mint operator-() const { return Mint(m - v); }
};
int Mint::m = mod;
struct point
{
int x, y;
typedef point P;
point(int x = 0, int y = 0) : x(x), y(y) {};
friend istream &operator>>(istream &inp, P &a)
{
int x1, y1;
inp >> x1 >> y1;
a.x = x1;
a.y = y1;
return inp;
}
friend ostream &operator<<(ostream &output, const P &p)
{
output << p.x << " " << p.y;
return output;
}
P operator+(const P o) const
{
return P(x + o.x, y + o.y);
}
P operator-(const P o) const
{
return P(x - o.x, y - o.y);
}
P &operator+=(const point &o)
{
x += o.x;
y += o.y;
return *this;
}
P &operator-=(const point &o)
{
x -= o.x;
y -= o.y;
return *this;
}
bool operator==(const P o) const
{
return {x == o.x && y == o.y};
}
bool operator!=(const P o) const
{
return !(*this == o);
}
bool operator<(const P o) const
{
return x < o.x || (x == o.x && y < o.y);
}
bool operator<=(const P o) const
{
return (*this < o || *this == o);
}
bool operator>(const P o) const
{
return !(*this <= o);
}
bool operator>=(const P o) const
{
return !(*this < o);
}
ll dot(const P o) const
{
return (1ll * x * o.x + 1ll * y * o.y);
}
ll cross(const P o) const
{
return (1ll * x * o.y - 1ll * y * o.x);
}
ll len2() const
{
return (1ll * x * x + 1ll * y * y);
}
ld len() const
{
return sqrtl(1ll * x * x + 1ll * y * y);
}
ld dist(const P o) const
{
return (o - *this).len();
}
ll dist2(const P o) const
{
return (o - *this).len2();
}
P operator*(const int k)
{
P b = *this;
b.x *= k;
b.y *= k;
return b;
}
P &operator*=(const int k)
{
(*this).x *= k;
(*this).y *= k;
return (*this);
}
P reflect(P x)
{
point h = x - *this;
h *= 2;
return (*this) + h;
}
};
struct circle
{
point p;
int r;
circle(point p = {0, 0}, int r = 0) : p(p), r(r) {};
friend istream &operator>>(istream &in, circle &c)
{
in >> c.p >> c.r;
return in;
}
friend std::ostream &operator<<(std::ostream &out, const circle &c)
{
out << c.p << " " << c.r;
return out;
}
bool tg(const circle o) const
{
ll d2 = p.dist2(o.p);
if (d2 == 1ll * (r + o.r) * (r + o.r))
return true;
else
return false;
}
};
template<typename T>
void chmax(T &a, T b)
{
if(a < b)
a = b;
}
template <typename T>
void chmin(T &a, T b)
{
if (a > b)
a = b;
}
template <typename T, typename U>
T SUM(const U &A)
{
return std::accumulate(A.begin(), A.end(), T{});
}
void print(long long t) { cerr << t; }
void print(int t) { cerr << t; }
void print(string t) { cerr << t; }
void print(char t) { cerr << t; }
void print(double t) { cerr << t; }
void print(long double t) { cerr << t; }
void print(unsigned long long t) { cerr << t; }
void print(point t) { cerr << "{" << t.x << "," << t.y << "}"; }
template <class T, class V>
void print(pair<T, V> p);
template <class T>
void print(vector<T> v);
template <class T>
void print(set<T> v);
template <class T, class V>
void print(map<T, V> v);
template <class T>
void print(multiset<T> v);
template <class T, class V>
void print(T v[], V n)
{
cerr << "[";
for (int i = 0; i < n; i++)
{
cerr << v[i] << " ";
}
cerr << "]";
}
template <class T, class V>
void print(pair<T, V> p)
{
cerr << "{";
print(p.first);
cerr << ",";
print(p.second);
cerr << "}";
}
template <class T>
void print(vector<T> v)
{
cerr << "[ ";
for (T i : v)
{
print(i);
cerr << " ";
}
cerr << "]";
}
template <class T>
void print(set<T> v)
{
cerr << "[ ";
for (T i : v)
{
print(i);
cerr << " ";
}
cerr << "]";
}
template <class T>
void print(multiset<T> v)
{
cerr << "[ ";
for (T i : v)
{
print(i);
cerr << " ";
}
cerr << "]";
}
template <class T, class V>
void print(map<T, V> v)
{
cerr << "[ ";
for (auto i : v)
{
print(i);
cerr << " ";
}
cerr << "]";
}
ll gcdll(ll a, ll b) { return b == 0 ? a : gcdll(b, a % b); }
long long binpow(long long a, long long b)
{
long long res = 1;
a %= mod;
while (b > 0)
{
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
const ld eps = 1e-6;
const int N = 1e4 + 67;
const int X = 10 + 67;
const int inf = 1e9;
struct S
{
int n__;
const int INFFFFF = 1e9;
struct node
{
int mx, mn;
int mx_pos, mn_pos;
} null = {0, INFFFFF, -1, -1};
node merge(node a, node b)
{
node x;
if (a.mn < b.mn)
x.mn = a.mn, x.mn_pos = a.mn_pos;
else
x.mn = b.mn, x.mn_pos = b.mn_pos;
if (a.mx > b.mx)
x.mx = a.mx, x.mx_pos = a.mx_pos;
else
x.mx = b.mx, x.mx_pos = b.mx_pos;
return x;
}
vector<node> t;
void _init(int _n)
{
n__ = _n;
t.resize(4 * n__, null);
}
void update(int x, int lx, int rx, int pos, int val)
{
if (pos > rx || pos < lx)
return;
if (lx == rx)
{
t[x] = {val, val, pos, pos};
return;
}
int mid = (lx + rx) / 2;
update(2 * x, lx, mid, pos, val);
update(2 * x + 1, mid + 1, rx, pos, val);
t[x] = merge(t[2 * x], t[2 * x + 1]);
}
node query(int x, int lx, int rx, int l, int r)
{
if (lx > r || rx < l)
return null;
if (lx >= l && rx <= r)
return t[x];
int mid = (lx + rx) / 2;
node ans_l = query(2 * x, lx, mid, l, r);
node ans_r = query(2 * x + 1, mid + 1, rx, l, r);
return merge(ans_l, ans_r);
}
};
int a[N], pos[N], dp[N];
struct fenwick
{
int f[N];
int n;
void init(int _n)
{
n = _n;
for (int i = 0; i <= n;i++)
f[i] = 0;
}
void upd(int pos, int val)
{
for (int i = pos; i <= n;i+=(i & (-i)))
{
f[i] += val;
}
}
int prefix_query(int ind)
{
int ans = 0;
for (int i = ind; i >= 1;i -= (i &(-i)))
{
ans += f[i];
}
return ans;
}
}ign, fen;
void solve()
{
int n;
cin >> n;
ign.init(n);
for (int i = 1; i <= n;i++)
{
cin >> a[i];
pos[a[i]] = i;
ign.upd(i, 1);
}
dp[0] = dp[1] = 0;
ign.upd(pos[1], -1);
for (int i = 2; i <= n;i++)
{
dp[i] = inf;
ign.upd(pos[i], -1);
int s = 0;
fen.init(n);
for (int j = i; j >= 1;j--)
{
s = s - fen.prefix_query(pos[j]) + i - (pos[j] - ign.prefix_query(pos[j]));
fen.upd(pos[j], 1);
chmin(dp[i], dp[j - 1] + s);
}
}
cout << dp[n] << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// increaseStack(512L * 1024L * 1024L);
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
