/*
TASK:psort
LANG:C
*/
#include <stdio.h>

int n;
int a[ 65536 ];
int L[ 65536 ];

int solve( )
{	int i, j, res=1, l, r, m;
	L[ 1 ] = a[ 1 ];
	for ( i=2; i<=n; i++ )
	{ 	if ( a[ i ] < L[ 1 ] ) L[ 1 ] = a[ i ];
		else
		if ( a[ i ] > L[ res ] )
		{	L[ ++res ] = a[ i ];	}
		else
		{ 	l = 1; r = res; m = ( l+r ) / 2;
			while ( r - l > 1 )
			{ m = ( l+r ) / 2;
			  if ( L[ m ] > a[ i ] )
			  	r = m;
			  else
			   l = m;
			}
		  L[ r ] = a[ i ];
		}
	}
	return res;
}

int main( )
{
	int i, ans;
	scanf( "%d", &n );
	for ( i=1; i<=n; i++ )
		scanf( "%d", a+i );
	ans = n - solve( );
	printf( "%d\n", ans );
	
	return 0;
}
