#include <bits/stdc++.h>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define rep(i, a, b) for (int i = (a), I = (b); i <= I; ++i)
#define per(i, a, b) for (int i = (a), I = (b); i >= I; --i)
using i64 = long long;
using pii = pair<int, int>;
template<typename T> void up(T &x, T y) { if (x < y) x = y; }
template<typename T> void down(T &x, T y) { if (x > y) x = y; }

const int N = 500005;
int n, a[N], b[N], m, f[N], c[N], sz[N], l[N], r[N], ptr[N];
vector<int> seq[N];
bool vis[N];

void modify(int p, int x) {
    for (; p <= m; p += p & -p) up(c[p], x);
}
int query(int p) {
    int res = 0;
    for (; p; p -= p & -p) up(res, c[p]);
    return res;
}

bool check(int i, int j) {
    return i < j && a[i] < a[j];
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> n;
    rep(i, 1, n) {
        cin >> a[i];
        b[++m] = a[i];
    }
    sort(b + 1, b + m + 1);
    m = unique(b + 1, b + m + 1) - b - 1;
    
    rep(i, 1, n) {
        a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
        f[i] = query(a[i] - 1) + 1;
        modify(a[i], f[i]);
        seq[f[i]].push_back(i);
    }

    int D = *max_element(f + 1, f + n + 1);
    sz[D] = seq[D].size();
    per(d, D - 1, 1) {
        int p1 = 0, p2 = -1;
        vector<int> tmp;
        for (auto i : seq[d]) {
            while (p1 < sz[d + 1] && seq[d + 1][p1] < i) ++p1;
            while (p2 + 1 < sz[d + 1] && a[seq[d + 1][p2 + 1]] > a[i]) ++p2;
            // cerr << "? " << i << " " << p1 << " " << p2 << "\n";
            l[i] = p1, r[i] = p2;
            if (l[i] <= r[i]) tmp.push_back(i);
        }
        seq[d] = tmp;
        sz[d] = seq[d].size();
    }

    int ans = 0;
    while (1) {
        bool flag = true;
        per(d, D, 1) {
            while (ptr[d] < sz[d]) {
                int i = seq[d][ptr[d]];
                if (vis[i] || r[i] < ptr[d + 1]) ++ptr[d];
                else break;
            }
            // cerr << "? " << d << " " << ptr[d] << " " << sz[d] << "\n";
            if (ptr[d] == sz[d]) {
                flag = false;
                break;
            }
        }
        if (!flag) break;
        rep(d, 1, D) {
            int i = seq[d][ptr[d]];
            vis[i] = true;
            if (d < D) up(ptr[d + 1], l[i]);
        }
        ++ans;
    }
    cout << n - ans << "\n";

    return 0;
}