#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;


int a[100010];
int p[100010];
int sum[100010];
int ans = 0,n;


int main()
{
	cin>>n;
	for(int i = 0; i<n; i++) 
	{
		cin>>a[i];
		p[a[i]] = i;
	}
	for(int i = 0; i<n; i++)
	{
		if(p[a[i]-1]<i)
		{
			sum[i] = sum[p[a[i]-1]]+1;
		}
		else sum[i] = 1;
	}
	for(int i = 0; i<n; i++)
		ans = max(sum[i],ans);
	cout<<n - ans<<endl;
	return 0;
}