stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;



struct number

{

	int a;

	int b;

};



bool compare(number a, number b)

{

	return a.a < b.a;

}



int N[201000], dp[201000];

number num[201000];



int main ()

{

	int n;

	cin >> n;

	

	if(n == 1)

	{

		cout << "0" << endl;

		return 0;

	}

	

	for(int i = 0; i < 201000; i++)

	{

		N[i] = 0;

		dp[i] = 1;

		num[i].a = 0;

		num[i].b = 0;

	}

	

	int x;

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

	{

		scanf("%d", &x);

		N[i] = x;

		num[i].a = x;

		num[i].b = i;

	}

	

	sort(num, num + n, compare);

	

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

//		cout << num[i].a << " " << num[i].b << endl;

	

	int max = 0;

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

	{

		if(num[i].b > num[i - 1].b)

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

		

		if(dp[i] > max)

			max = dp[i];

	}

	

	cout << n - max << endl;

	

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.281075588793511x):
#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn =(int)2e5+7;

int a[maxn];

int b[maxn];

int dp[maxn];

int DP_LIS(int n)// NLOGN LIS

{

	if(n==0)return 0;//ery important!!

	int len;

	dp[1]=a[1];

	len=1;

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

	{

		if(a[i]>dp[len])dp[++len]=a[i];

		else

		{

			int pos=lower_bound(dp,dp+len,a[i])-dp;

			dp[pos]=a[i];

		}

	}

	return len;

}



int main()

{

	int n;

	cin>>n;

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

	{

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

		b[a[i]]=i; 

	}

	//for(int i=1;i<=n;i++)cout<<b[i]<< " "; 

	for(int i=1;i<=n;i++)a[i]=b[i];

	int mx=0;

	int cnt=1; 

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

	{

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

		else{

			mx=max(mx,cnt);

			cnt=1;

		}

		mx=max(mx,cnt);

	}

	cout<<n-mx<<endl;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;



struct number

{

	int a;

	int b;

};



bool compare(number a, number b)

{

	return a.a < b.a;

}



int N[201000], dp[201000];

number num[201000];



int main ()

{

	int n;

	cin >> n;

	

	if(n == 1)

	{

		cout << "0" << endl;

		return 0;

	}

	

	for(int i = 0; i < 201000; i++)

	{

		N[i] = 0;

		dp[i] = 1;

		num[i].a = 0;

		num[i].b = 0;

	}

	

	int x;

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

	{

		scanf("%d", &x);

		N[i] = x;

		num[i].a = x;

		num[i].b = i;

	}

	

	sort(num, num + n, compare);

	

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

//		cout << num[i].a << " " << num[i].b << endl;

	

	int max = 0;

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

	{

		if(num[i].b > num[i - 1].b)

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

		

		if(dp[i] > max)

			max = dp[i];

	}

	

	cout << n - max << endl;

	

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.185979013278362x):
#include <iostream>

#include <algorithm>

#include <stack>

#include <stdio.h>

#include <string.h>

#include <ctype.h>

#include <cmath>

#define FOR(i,a,b)    for ( int i = (a), _n = (b); i < _n; i++ )

#define FORD(i,a,b)   for ( int i = (a), _n = (b); i > _n; i-- )

#define FORS(i,a,b,c) for ( int i = (a), _n = (b); i < _n; i += c )

#define FOREACH(p,s)  for ( __typeof((s).begin()) p=(s).begin(); p!=(s).end(); p++)

typedef long long ll;



using namespace std;



int main()

{

    ios::sync_with_stdio(false);

    int dp[200005],maxi = 1;

    int n,a,c = 1;

    cin >> n;

    FOR(i,0,n)

    {

    	cin >> a;

//    	cout << a[i] << endl;

    	dp[a] = i;

	}

	FOR(i,1,n)

	{

//		cout << dp[i] <<endl;

	    if(dp[i+1] > dp[i])

	    {

	    	c++;

		}

		else

		{

			c = 1;

		}

//		cout << c << endl;

		if(maxi < c)

        {

            maxi = c;

        }

	}

	cout << n - maxi;

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;



struct number

{

	int a;

	int b;

};



bool compare(number a, number b)

{

	return a.a < b.a;

}



int N[201000], dp[201000];

number num[201000];



int main ()

{

	int n;

	cin >> n;

	

	if(n == 1)

	{

		cout << "0" << endl;

		return 0;

	}

	

	for(int i = 0; i < 201000; i++)

	{

		N[i] = 0;

		dp[i] = 1;

		num[i].a = 0;

		num[i].b = 0;

	}

	

	int x;

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

	{

		scanf("%d", &x);

		N[i] = x;

		num[i].a = x;

		num[i].b = i;

	}

	

	sort(num, num + n, compare);

	

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

//		cout << num[i].a << " " << num[i].b << endl;

	

	int max = 0;

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

	{

		if(num[i].b > num[i - 1].b)

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

		

		if(dp[i] > max)

			max = dp[i];

	}

	

	cout << n - max << endl;

	

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.2336471886503055x):
//#include<cstdio>

//#include<cassert>

//#include<iostream>

//#include<cstring>

//#include<algorithm>

#include<bits/stdc++.h>

#include<ext/pb_ds/assoc_container.hpp>

#include<ext/pb_ds/tree_policy.hpp>

#define MAX ((int)1e9 + 5)

#define MAXL ((ll)3e18 + 7)

#define MAX_X ((ll)1e5 + 2)

#define pi (2.0*acos(0))

#define M ((int)1e6 + 7)

#define MOD ((int)1e9 + 7)

#define NN ((int)3e6 + 7)

#define N ((int)2e5 + 5)

#define eps (0)

#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)

#define logn 29

#define endl "\n"

#define mp make_pair

#define BUCK 105

#define RIG ((idx<<1)|1)

#define LEF (idx<<1)

//#define int ll





using namespace std;

using namespace __gnu_pbds;



typedef long long ll;

typedef unsigned long long ull;

typedef unsigned int uint;



/*fast io

ios_base::sync_with_stdio(false);

cin.tie(NULL);

*/









typedef tree < int,  null_type,  less < int >,  rb_tree_tag,  tree_order_statistics_node_update > o_set;

/// o_set s;

/// s.order_of_key(k) : Number of items strictly smaller than k .

/// *(s.find_by_order(k)) : K-th element in a set (counting from zero).





int arr[N] , nxt[N] , pos[N];





int main()

{

    fastio;

    int n ;

    cin>>n;

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

        cin>>arr[i];

        pos[arr[i]] = i;

    }

    nxt[n] = n+1;

    for(int i = n-1 ; i>0; i--){

        if(pos[i+1]<pos[i]) nxt[i] = i+1;

        else nxt[i] = nxt[i+1];

    }

    int ans = n+1-nxt[1];

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

        ans = min(ans , i + n+1 - nxt[i+1]);

    }

    cout<<ans<<endl;

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;



struct number

{

	int a;

	int b;

};



bool compare(number a, number b)

{

	return a.a < b.a;

}



int N[201000], dp[201000];

number num[201000];



int main ()

{

	int n;

	cin >> n;

	

	if(n == 1)

	{

		cout << "0" << endl;

		return 0;

	}

	

	for(int i = 0; i < 201000; i++)

	{

		N[i] = 0;

		dp[i] = 1;

		num[i].a = 0;

		num[i].b = 0;

	}

	

	int x;

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

	{

		scanf("%d", &x);

		N[i] = x;

		num[i].a = x;

		num[i].b = i;

	}

	

	sort(num, num + n, compare);

	

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

//		cout << num[i].a << " " << num[i].b << endl;

	

	int max = 0;

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

	{

		if(num[i].b > num[i - 1].b)

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

		

		if(dp[i] > max)

			max = dp[i];

	}

	

	cout << n - max << endl;

	

	return 0;

}

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

using namespace std;

const int MAXN = 2e5+7;



int p[MAXN];

int r[MAXN];



int main() {

    int n;

    cin >> n;



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

        cin >> p[i];

        r[p[i]] = i;

    }



    int ans = 1;

    int run = 1;

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

        if (r[i-1] < r[i]) run++;

        else run = 1;

        ans = max(ans, run);

    }



    cout << n-ans << "\n";





    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;



struct number

{

	int a;

	int b;

};



bool compare(number a, number b)

{

	return a.a < b.a;

}



int N[201000], dp[201000];

number num[201000];



int main ()

{

	int n;

	cin >> n;

	

	if(n == 1)

	{

		cout << "0" << endl;

		return 0;

	}

	

	for(int i = 0; i < 201000; i++)

	{

		N[i] = 0;

		dp[i] = 1;

		num[i].a = 0;

		num[i].b = 0;

	}

	

	int x;

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

	{

		scanf("%d", &x);

		N[i] = x;

		num[i].a = x;

		num[i].b = i;

	}

	

	sort(num, num + n, compare);

	

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

//		cout << num[i].a << " " << num[i].b << endl;

	

	int max = 0;

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

	{

		if(num[i].b > num[i - 1].b)

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

		

		if(dp[i] > max)

			max = dp[i];

	}

	

	cout << n - max << endl;

	

	return 0;

}

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

//#include <ext/pb_ds/assoc_container.hpp>

//using namespace __gnu_pbds;

using namespace std;

typedef long long ll;

//typedef tree<int,null_type,less<int >,rb_tree_tag,tree_order_statistics_node_update>indexed_set;

template<class T1, class T2>

ostream &operator <<(ostream &os, pair<T1,T2>&p);

template <class T>

ostream &operator <<(ostream &os, vector<T>&v);

template <class T>

ostream &operator <<(ostream &os, set<T>&v);

#define debug(a) cerr<<#a<<" --> "<<(a)<<endl;

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

#define INPUT freopen("input.txt","r",stdin)

#define OUTPUT freopen("output.txt","w",stdout)

#define ERROR  1e-9

#define pi (2*acos(0))

const ll mod = 998244353;

const int N = 1e5 +5;





void SOLVE(int cas)

{

    int n;

    scanf("%d",&n);

    vector<int>v(n),decrease(n),pos(n,-1);

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

    {

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

        v[i]--;



    }

    int maxi =0;

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

    {

        if(v[i]==0 || pos[v[i]-1]==-1)

        {

            decrease[v[i]] = 1;

        }

        else{

            decrease[v[i]] = 1+ decrease[v[i]-1];

        }

        pos[v[i]]=i;

    }

    maxi = *max_element(decrease.begin(),decrease.end());

    int ans = n-maxi;

    printf("%d\n",ans);

}





/*





*/







int main()

{

    //INPUT;

    //OUTPUT;

    int t=1,cas=0;

    //scanf("%d",&t);

    while(t--)

    {

        SOLVE(++cas);

    }



    return 0;

}







//os.order_of_key(v): returns how many elements strictly less than v

//os.find_by_order()



template<class T1, class T2>

ostream &operator <<(ostream &os, pair<T1,T2>&p)

{

    os<<"{"<<p.first<<", "<<p.second<<"} ";

    return os;

}

template <class T>

ostream &operator <<(ostream &os, vector<T>&v)

{

    os<<"[ ";

    for(int i=0; i<v.size(); i++)

    {

        os<<v[i]<<" " ;

    }

    os<<" ]";

    return os;

}



template <class T>

ostream &operator <<(ostream &os, set<T>&v)

{

    os<<"[ ";

    for(T i:v)

    {

        os<<i<<" ";

    }

    os<<" ]";

    return os;

}
// 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.475507652377183x):
#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

using namespace std;

int n;

int a[210000],f[210000],ans;

int main()

{

	scanf("%d",&n);

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

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

	ans=n;

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

	{

	  f[a[i]]=max(1,f[a[i]-1]+1);

	  ans=min(ans,n-a[i]+a[i]-f[a[i]]);

	}

	printf("%d\n",ans);

}
// 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: 38.68167773400166x):
#include <cstdio>

#include<cstring>

#include <algorithm>

using  namespace std;

#define mem(v,x) memset(v,x,sizeof(v))

#define low(x) (x & (-x))

int pos[500010],n,m;



int main() {

    scanf("%d",&n);

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

       scanf("%d",&m);

       pos[m] = i;

    }

    int len = 1,ans = 5000000;

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

        if (pos[i+1] > pos[i]) len++; else{

            ans = min(ans,n-len);

            len = 1;

        }

    }

    ans = min(ans,n-len);

    printf("%d\n",ans);



    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

using namespace std;

int n;

int a[210000],f[210000],ans;

int main()

{

	scanf("%d",&n);

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

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

	ans=n;

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

	{

	  f[a[i]]=max(1,f[a[i]-1]+1);

	  ans=min(ans,n-a[i]+a[i]-f[a[i]]);

	}

	printf("%d\n",ans);

}

// Faster C++ solution for the same problem (measured speedup: 5.1744549711886165x):
#include <cstdio>

#include<cstring>

#include <algorithm>

using  namespace std;

#define mem(v,x) memset(v,x,sizeof(v))

#define low(x) (x & (-x))

int pos[500010],n,m;



int main() {

    scanf("%d",&n);

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

       scanf("%d",&m);

       pos[m] = i;

    }

    int len = 1,ans = 5000000;

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

        if (pos[i+1] > pos[i]) len++; else{

            ans = min(ans,n-len);

            len = 1;

        }

    }

    ans = min(ans,n-len);

    printf("%d\n",ans);



    return 0;

}
// 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.478052564086777x):
#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 200000+100;



int n,tmp;

int a[maxn];



int main()

{

	scanf("%d",&n);

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

	{

		scanf("%d",&tmp);

		a[tmp] = i;

	}

	int ans = 1;

	int k = 1;

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

	{

		k = 1;

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

		{

			i++;

			k++;

		}

		ans = max(ans,k);

	}

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

	return 0;

}
// 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.478533159570051x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int SIZE = 200010;

int n;

int num[SIZE],pos[SIZE];



int main()

{

	scanf("%d",&n);

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

	{

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

		pos[num[i]] = i;

	}

	int ans = 0,len = 1;

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

	{

		if(pos[i] < pos[i-1])

		{

			ans = max(ans,len);

			len = 1;

		}

		else	len++;

	}

	ans = max(ans,len);

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

 	return 0;

}
// 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.385950021439365x):
#include<bits/stdc++.h>

using namespace std;

 

int main()

{

  int n;

  cin >> n;

  int x;

  int arr[n];

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

    cin >> x;

    arr[x - 1] = i;

  }

  if(n == 1) {

    cout << 0 << endl;

    return 0;

  }

  int mx = 0 , cur = 1;

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

    if(arr[i - 1] < arr[i]) cur++;

    else cur = 1;

    mx = max(mx , cur);

  }

  cout << n - mx << endl;

}
// 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.391018402188674x):
#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include <complex>

using namespace std;







#define FOR(i,a,b) for (int i = (a); i < (b); i++)

#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



#define SZ(a) (int)a.size()

#define ALL(a) a.begin(), a.end()

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL)INF;



const double EPS = 1e-8;

const int MOD = 1000 * 1000 * 1000 + 7;

const int MAX = 2*1000 * 100 + 47;

const int LEN = 20;

const int ALP = 128;



int DP[MAX];

int main()

{

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

    int n;

    scanf("%d", &n);

    FOR(i, 0, n) {

        int x;

        scanf("%d", &x);

        DP[x] = DP[x-1]+1;

    }

    int res = n - *max_element(DP, DP + n + 1);

    cout << res << endl;

    

    

    return 0;

}
// 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.457274340287778x):
#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<queue>

#define LL long long

#define inl inline

#define re register

#define MAXN 200100

using namespace std;

int n;

int p[MAXN];

int t[MAXN];

int f[MAXN];

int ans;

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)scanf("%d",&p[i]),t[p[i]]=i;

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

	{

		if(t[p[i]-1]<t[p[i]])f[p[i]]=f[p[i]-1]+1;

		else f[p[i]]=1;

	}

	for(int i=1;i<=n;i++)ans=max(ans,f[i]);

	cout<<n-ans;

	return 0;

}