#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

int main(){
    int n;
    cin >> n;

    vector<int> szamok(n, 0);
    for(int i = 0; i < n; i++){
        cin >> szamok[i];
    }

    int db = 1;
    vector<pii> kezdok;
    vector<int> indexek(n, -1);
    kezdok.push_back({szamok[0], 0});
    for(int i = 1; i < n; i++){
        if(szamok[i] != szamok[i - 1] + 1){
            db++;
            kezdok.push_back({szamok[i], i});
        }
    }

    sort(kezdok.begin(), kezdok.end());

    for(int i = 0; i < kezdok.size(); i++){
        indexek[kezdok[i].second] = i;
    }

    vector<int> uj;
    int utolso = 0;
    vector<int> meretek(db, 0);
    for(int i = 0; i < n; i++){
        if(indexek[i] != -1){
            uj.push_back(indexek[i]);
            utolso = indexek[i];
        }
        meretek[utolso]++;
    }

    vector<bool> latta(db, 0);
    vector<int> minusz(db, 0);
    for(int i = 1; i < db; i++){
        if(latta[i - 1]){
            minusz[i] += meretek[i - 1];
        }
        latta[i] = 1;
    }

    latta.assign(db, 0);
    for(int i = db - 2; i >= 0; i--){
        if(latta[i + 1]){
            minusz[i] += meretek[i + 1];
        }
        latta[i] = 1;
    }

    for(int i = 0; i < db; i++){
        minusz[i] += meretek[i];
    }

    int maxi = 0;
    for(int i = 0; i < db; i++){
        maxi = max(maxi, minusz[i]);
    }

    cout << n - maxi << "\n";
}