#include <iostream>
using namespace std;
int
x[200001], n, ans, f[200001];
void
__read__()
{
cin >> n;
for( int i = 1; i <= n; i++ )
cin >> x[i];
}
void
__lis__()
{
for( int i = 1; i <= n; i++ )
{
f[i] = 999999999;
int
p = 1, q = 1 + ans, k = 0;
while( p <= q )
{
k = ( p + q ) / 2;
if( x[i] <= f[k] && x[i] > f[k - 1] )
break;
if( x[i] > f[k] )
p = k + 1;
else
q = k - 1;
}
f[k] = x[i];
if( k > ans )
ans = k;
}
}
void
__outp__()
{
cout << n - ans << endl;
}
int
main()
{
__read__();
__lis__();
__outp__();
return 0;
}