#include <stdio.h>
#include <stdlib.h>

// Cari panjang LIS dengan binary search (O(N log N))
int lis_length(int *A, int n) {
    int *tails = (int *)malloc(n * sizeof(int));
    int len = 0;

    for (int i = 0; i < n; i++) {
        // Binary search: cari posisi terkecil di tails yang >= A[i]
        int lo = 0, hi = len;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (tails[mid] < A[i])
                lo = mid + 1;
            else
                hi = mid;
        }
        tails[lo] = A[i];
        if (lo == len) len++;
    }

    free(tails);
    return len;
}

int main() {
    int n;
    scanf("%d", &n);

    int *A = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++)
        scanf("%d", &A[i]);

    int langkah = n - lis_length(A, n);
    printf("%d\n", langkah);

    free(A);
    return 0;
}