#include<stdio.h>
long i,n,j,lung,maxim,k,max,a[5001],s[5001];
FILE *f,*g;
int main()
{ f=fopen("secv.in","r"); g=fopen("secv.out","w");
  fscanf(f,"%d",&n);
  for(i=1;i<=n;i++) fscanf(f,"%ld",&a[i]);
  maxim=0;
  for(i=n;i>=1;i--)
   { max=0;
     for(j=i+1;j<=n;j++) if(s[j]>max&&a[j]>a[i]) max=s[j];
     s[i]=max+1;
     if(s[i]>maxim) maxim=s[i];
   }
  lung=n;
  for(i=1;i<=n;i++)
   if(s[i]==maxim)
    { k=maxim-1; j=i;
      while(k!=0)
       { j++;
	 if(s[j]==k) k--;
       }
      if(j-i+1<lung) lung=j-i+1;
    }
  fprintf(g,"%ld",lung);
  fclose(g);
  return 0;
}