#include<iostream>
using namespace std;

int a[31000],d[31000],g[31000];

int main()
{
	int n,i;
	cin>>n;
	for (i=0; i<n; i++){
		cin>>a[i];
		d[i]=1;
	}
	
	for (i=1; i<=n; i++) g[i]=n+1;
	for (i=0; i<n; i++){
		int k=lower_bound(g+1,g+n+1,a[i])-g;
		d[i]=k;
		g[k]=a[i];
	}
	
	int ans=1;
	for (i=0; i<n; i++) if (ans<d[i]) ans=d[i];
	ans=n-ans+1;
	
	cout<<ans;
	
	return 0;
}