
/*
TASK: psort
LANG: C
*/

#include<stdio.h>

#define MAXN 131072

int get_max(int ,int ,int ,int , int );
void put_max(int ,int );

int index_tree[MAXN]={0};
int size=1,n,a;
int i,curmax,max=0,j;

int main () {
//        FILE *fi;
//        fi=fopen("test.txt","rt");
//        fscanf(fi,"%d",&n);
        scanf("%d",&n);
        while (size<n) size<<=1;
        size-=1;
        for (i=0;i<n;i++) {
                //fscanf(fi,"%d",&a);
                scanf("%d",&a);
                curmax=get_max(0,1,size+1,1,a)+1;
                if (curmax>max) max=curmax;
                put_max(size+a-1,curmax);
                }
        printf("%d\n",n-max);
        return 0;
        }

int get_max(int cp,int s,int e,int rs, int re) {
        int mid,max1=0,max2=0;
        if (rs<=s&&e<=re) return index_tree[cp];
        else if (s<e) {
                        mid=(s+e)/2;
                        if (rs<=mid) max1=get_max(2*cp+1,s,mid,rs,re);
                        if (re>mid) max2=get_max(2*cp+2,mid+1,e,rs,re);
                        return max1>max2?max1:max2;
                        }
        }
        
void put_max(int cp,int val) {
        index_tree[cp]=val;
        do {
                cp=(cp-1)/2;
                index_tree[cp]=index_tree[cp]<val?val:index_tree[cp];
                } while (cp);
        }
