#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int min_moves_to_sort_cars(int N, vector<int>& P) {
    vector<int> position(N + 1);
    for (int i = 0; i < N; ++i) {
        position[P[i]] = i;
    }
    int lis_length = 1;
    int current_length = 1;
    for (int i = 2; i <= N; ++i) {
        if (position[i] > position[i - 1]) {
            current_length++;
            lis_length = max(lis_length, current_length);
        } else {
            current_length = 1;
        }
    }

    int min_moves = N - lis_length;
    return min_moves;
}

int main() {
    int N;
    cin >> N;
    vector<int> P(N);
    for (int i = 0; i < N; ++i) {
        cin >> P[i];
    }

    int result = min_moves_to_sort_cars(N, P);
    cout << result << endl;

    return 0;
}