#include<iostream>
using namespace std;
int a[200005],b[200005],c[200005];
int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        c[a[i]]=i;
        b[i]=1;
    }
    for(int i=2;i<n;i++)
    {
        if(c[a[i]]>c[a[i]-1])
        {
            b[a[i]]=b[a[i]-1]+1;
            ans=max(ans,b[a[i]]);
        }
    }
    ans=n-ans;
    cout<<ans;
    return 0;
}
