#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

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

    unordered_map<int, int> pos;
    for (int i = 0; i < N; ++i) {
        pos[arr[i]] = i;
    }

    int max_sorted_len = 1, current_length = 1;

    for (int i = 2; i <= N; ++i) {
        if (pos[i] > pos[i - 1]) {
            current_length++;
        } else {
            current_length = 1; // reset
        }
        max_sorted_len = max(max_sorted_len, current_length);
    }

    cout << N - max_sorted_len << endl;
    return 0;
}