// Slower C++ solution:
//#include<bits/stdc++.h> 

#include<iostream> 

#include<cstdio>

#include<cstring>

#include<queue>

#include<vector>  

#define Max int(2e5+10) 

using namespace std;  

int n,p[Max],a[Max],dp[Max];

vector<int> g[Max];

int dfs(int x)

{

	if(dp[x]>0)

	   return dp[x];

	dp[x]=1;

	for(int i=0;i<g[x].size();i++)

	    dp[x]=dfs(g[x][i])+1;

	 return dp[x];	  

}

int  main()  

{   

    while(~scanf("%d",&n))

    {

    	for(int i=1;i<=n;i++)

    	    g[i].clear();

    	for(int i=1;i<=n;i++)

    	   {

    	   	scanf("%d",&p[i]);

    	   	a[p[i]]=i;

		   }

    	for(int i=1;i<n;i++)

		    if(a[i]<a[i+1])

		       g[a[i]].push_back(a[i+1]);

	//	for(int i=1;i<=n;i++)

	//	   cout<<g[i][0]<<endl; 	       

		memset(dp,0,sizeof dp);   

		int ma=-1;      

    	for(int i=1;i<=n;i++)

		   ma=max(ma,dfs(i));

		//cout<<ma<<endl;   

		printf("%d\n",n-ma);   

	}

      

       

     return 0;     

} 

// Faster C++ solution for the same problem (measured speedup: 7.230766300081871x):
#include<bits/stdc++.h>

using namespace std;



typedef long long int lli;

typedef unsigned long long int ulli;

typedef pair<int,int> pii;

typedef priority_queue< int, vector< int >, greater< int > >  minHeap;



#define ones(x) __builtin_popcount(x)

#define onesl(x) __builtin_popcountl(x)

#define onesll(x) __builtin_popcountll(x)



#define pb push_back

#define eb emplace_back

#define mp make_pair

#define mt make_tuple

#define scn(n) scanf("%d",&n)

#define scnll(n) scanf("%lld",&n)

#define scn2(n,m) scanf("%d%d",&n,&m)

#define scn3(n,m,w) scanf("%d%d%d",&n,&m,&w)

#define scn2ll(n,m) scanf("%lld%lld",&n,&m)

#define atoz(v) v.begin(),v.end()

#define ratoz(v) v.rbegin(),v.rend()

#define Fill(a,v) memset(a,v,sizeof(a))

#define fi first

#define se second

#define inf 1e9

#define pi acos(-1.0)

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

#define mod 1000000007

#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define bug(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << "\n"



int Set(int N,int pos)

{

    return N=N | (1<<pos);

}

int reset(int N,int pos)

{

    return N = N & ~(1<<pos);

}

bool check(int N,int pos)

{

    return (bool)(N & (1<<pos));

}



inline int addmod(lli x,lli y)

{

    return (x%mod + y%mod)%mod;

}

inline int submod(lli x,lli y)

{

    return (x%mod - y%mod + mod)%mod;

}

inline int mulmod(lli x,lli y)

{

    return (x%mod * y%mod)%mod;

}





inline int nextSubMask(int i, int mask)

{

    return (i-1)&mask;   /// returns next  submask

}



template<typename T>

void we_r_done(T mssg)

{

    cout<<mssg;

    exit(0);

}



int main()

{

    ///freopen("output.txt","w",stdout);

   //freopen("input.txt","r",stdin);

    FastIO;



    int n;

    while(cin>>n){



        int a[n+1];

        vector<int>dp(n+5,0);



        for(int i=1; i<=n; i++){

            cin>>a[i];

            dp[a[i]] = dp[a[i]-1] + 1;

        }

        int mx = 0;

        for(int i=1; i<=n; i++){

            mx = max(dp[i],mx);

        }

        cout<<(n-mx)<<endl;

    }



    return 0;

}



///sin and cos expect input in radians not degrees. so use , sin(degrees * pi / 180)

///using bs = bitset<MX>; // how many distinct number can be form?

///sort(atoz(v), [](const data x, const data y){return (x.a==y.a?x.b>y.b : x.a<y.a);});