stablegradients/pie-gem5-pairs huggingface dataset:
// 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.485666273108606x):
#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<string>

#define ll long long

using namespace std;

int n,f[200005],a[200005];

int getnum()

{

    int ans=0;

    bool f=1;

    char c=getchar();

    while(!isdigit(c))

    {

        if(c=='-')f=0;

        c=getchar();

    }

    while(isdigit(c))

    {

        ans=ans*10+c-'0';

        c=getchar();

    }

    return f? ans : -ans;

}

int max(int a,int b)

{

    return a>b ? a : b;

}

int main()

{

    n=getnum();

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

    {

        a[i]=getnum();

        f[a[i]]=i;

    }

    int cnt=1,ans=1;

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

    {

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

        else cnt=1;

        ans=max(cnt,ans);

    }

    cout<<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.375916868057172x):
#include <iostream>

#include <cstring>

#include <cmath>

using namespace std;



int dfs(int * a,int& n,int lastNumber,int maxNumber,int currentLength,int lastIndex);

int main(){

	int n;

	cin>>n;

	int* a=new int[n];

	memset(a,0,sizeof(int)*n);

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

		cin>>a[i];

	}

	int *length=new int[n+1];

	memset(length,0,sizeof(int)*(n+1));

	int maxLength=0;

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

		if(length[a[i]-1]==0){

			length[a[i]]=1;

		}else{

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

		}

	}

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

		maxLength=max(maxLength,length[i+1]);

	}

	cout<<n-maxLength<<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.224459572455931x):
#include <bits/stdc++.h>

#define f first

#define s second



using namespace std;



typedef long long ll;



int main(){

    ios_base::sync_with_stdio(0); cin.tie(0);

    int n; cin >> n;

    vector <int> lis(n+1,0);

    int ans = 0;

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

        int cur; cin >> cur;

        lis[cur] = lis[cur-1] + 1;

        ans = max(ans, lis[cur]);

    }

    cout << n - ans << '\n';

    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.29740195378058x):
#include<iostream>

#include<vector>

#include<cstring>

#include<map>

#include<bitset>

#include<assert.h>

#include<algorithm>

#include<iomanip>

#include<cmath>

#include<set>

#include<queue>

#define long long long

using namespace std;

const int N=1e6,mod=1e9+7;

int aa[N+2],dp[N+2];

int main()

{

  ios_base::sync_with_stdio(0);cin.tie(0);

  int n;cin>>n;

  for(int i=1;i<=n;i++)cin>>aa[i];

  int mx=0;

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

  {

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

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

  }

  cout<<n-mx<<endl;

  return 0; 

}
// Slower C++ solution:


#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

int a[200005];

map<int, int>m;// [200005];//就相当于是int m[200005];

vector<int> g[200005];

int vis[200005]={0};

int maxn = 0;

int dfs(int i, int ans) {

	if(vis[i]!=0)return ans;

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

	{

		//if(!vis[i])

		ans = max(dfs(g[i][j], ans) + 1, ans);

	}

	vis[i]=ans;

	return ans;

}

int main() {

	int n; cin >> n;

	int x;

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

		cin >> x;

		m[x] = i;

	}

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

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

			//如果 i+1的下标比i要大, 就是在他后面

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

	}

	//建图完毕

	int ans = 0;

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

		ans = max(ans, dfs(i, 1));

	}

	cout << (n-ans)<<endl;//(最长的)

	return 0;

}


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

using namespace std;

#define mp make_pair

#define pb push_back

typedef pair<int,int> ii;

typedef long long ll;

typedef pair<ll,ll>l4 ;

const int maxn=2e5+5;

int n,a[maxn];

int main(){

	scanf("%d",&n);

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

	{

	    int x;

		scanf("%d",&x);

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

	}

	printf("%d\n",n-*max_element(a+1,a+1+n));

	return 0;

}
// Slower C++ solution:


#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

int a[200005];

map<int, int>m;// [200005];//就相当于是int m[200005];

vector<int> g[200005];

int vis[200005]={0};

int maxn = 0;

int dfs(int i, int ans) {

	if(vis[i]!=0)return ans;

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

	{

		//if(!vis[i])

		ans = max(dfs(g[i][j], ans) + 1, ans);

	}

	vis[i]=ans;

	return ans;

}

int main() {

	int n; cin >> n;

	int x;

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

		cin >> x;

		m[x] = i;

	}

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

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

			//如果 i+1的下标比i要大, 就是在他后面

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

	}

	//建图完毕

	int ans = 0;

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

		ans = max(ans, dfs(i, 1));

	}

	cout << (n-ans)<<endl;//(最长的)

	return 0;

}


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

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<cstdlib>



using namespace std;



const int N=200010;



struct B{

	int u,id;

	bool operator<(const B&rhs)const{

		return u<rhs.u;

	}

};



B b[N];



int n,a[N],aans;



int main(){

	scanf("%d",&n);

	if(n==1){

		printf("0\n");

		return 0;

	}

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

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

		b[i].u=a[i];

		b[i].id=i;

	}

	sort(b+1,b+1+n);

	int cnt=1;

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

		if(b[i].id>b[i-1].id){

			cnt++;

		}

		else{

			aans=max(cnt,aans);

			cnt=1;

		}

	}

	aans=max(cnt,aans);

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

	return 0;

}
// Slower C++ solution:


#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

int a[200005];

map<int, int>m;// [200005];//就相当于是int m[200005];

vector<int> g[200005];

int vis[200005]={0};

int maxn = 0;

int dfs(int i, int ans) {

	if(vis[i]!=0)return ans;

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

	{

		//if(!vis[i])

		ans = max(dfs(g[i][j], ans) + 1, ans);

	}

	vis[i]=ans;

	return ans;

}

int main() {

	int n; cin >> n;

	int x;

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

		cin >> x;

		m[x] = i;

	}

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

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

			//如果 i+1的下标比i要大, 就是在他后面

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

	}

	//建图完毕

	int ans = 0;

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

		ans = max(ans, dfs(i, 1));

	}

	cout << (n-ans)<<endl;//(最长的)

	return 0;

}


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

#include<iostream>

#include<cstring>

#include<string>

#include<cmath>

#include<algorithm>

#include<cstdlib>



using namespace std;



const int N=200010;



struct B{

	int u,id;

	bool operator<(const B&rhs)const{

		return u<rhs.u;

	}

};



B b[N];



int n,a[N],aans;



int main(){

	scanf("%d",&n);

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

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

		b[i].u=a[i];

		b[i].id=i;

	}

	if(n==1){

		printf("0\n");

		return 0;

	}

	sort(b+1,b+1+n);

	int cnt=1;

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

		if(b[i].id>b[i-1].id){

			cnt++;

		}

		else{

			aans=max(cnt,aans);

			cnt=1;

		}

	}

	aans=max(cnt,aans);

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

	return 0;

}
// Slower C++ solution:


#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

int a[200005];

map<int, int>m;// [200005];//就相当于是int m[200005];

vector<int> g[200005];

int vis[200005]={0};

int maxn = 0;

int dfs(int i, int ans) {

	if(vis[i]!=0)return ans;

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

	{

		//if(!vis[i])

		ans = max(dfs(g[i][j], ans) + 1, ans);

	}

	vis[i]=ans;

	return ans;

}

int main() {

	int n; cin >> n;

	int x;

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

		cin >> x;

		m[x] = i;

	}

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

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

			//如果 i+1的下标比i要大, 就是在他后面

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

	}

	//建图完毕

	int ans = 0;

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

		ans = max(ans, dfs(i, 1));

	}

	cout << (n-ans)<<endl;//(最长的)

	return 0;

}


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

#include<cstdio>

int a[200001];

int f[200001];

int cnt,l,r,mid,ans,maxn=0;

using namespace std;

int main(){

	int n;

	cin>>n;

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

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

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

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

		maxn=max(maxn,f[a[i]]);

	}

	cout<<n-maxn;

}
// Slower C++ solution:


#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

int a[200005];

map<int, int>m;// [200005];//就相当于是int m[200005];

vector<int> g[200005];

int vis[200005]={0};

int maxn = 0;

int dfs(int i, int ans) {

	if(vis[i]!=0)return ans;

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

	{

		//if(!vis[i])

		ans = max(dfs(g[i][j], ans) + 1, ans);

	}

	vis[i]=ans;

	return ans;

}

int main() {

	int n; cin >> n;

	int x;

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

		cin >> x;

		m[x] = i;

	}

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

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

			//如果 i+1的下标比i要大, 就是在他后面

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

	}

	//建图完毕

	int ans = 0;

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

		ans = max(ans, dfs(i, 1));

	}

	cout << (n-ans)<<endl;//(最长的)

	return 0;

}


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

#include<cstring>

#include<cstdio>

#include<string>

#include<algorithm>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<iomanip>

#define ll long long

#define For(i,a,n) for(register int i=a;i<=n;i++)

#define RF(i,a,n) for(register int i=a;i>=n;i--)

#define NIL -1

#define MAX 200005

using namespace std;

int n,ans;

int A[MAX];

int dp[MAX];

bool B[MAX];



int main(){

    ios::sync_with_stdio(false);

    cin>>n;

    For(i,1,n){

    	cin>>A[i];dp[i]=1;

    }

    For(i,1,n){

    	B[A[i]]=true;

    	if(B[A[i]-1]) dp[A[i]]=max(dp[A[i]],dp[A[i]-1]+1);

    	ans=max(ans,dp[A[i]]);

    }

    cout<<n-ans<<endl;

    return 0;

}
// Slower C++ solution:


#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

int a[200005];

map<int, int>m;// [200005];//就相当于是int m[200005];

vector<int> g[200005];

int vis[200005]={0};

int maxn = 0;

int dfs(int i, int ans) {

	if(vis[i]!=0)return ans;

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

	{

		//if(!vis[i])

		ans = max(dfs(g[i][j], ans) + 1, ans);

	}

	vis[i]=ans;

	return ans;

}

int main() {

	int n; cin >> n;

	int x;

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

		cin >> x;

		m[x] = i;

	}

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

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

			//如果 i+1的下标比i要大, 就是在他后面

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

	}

	//建图完毕

	int ans = 0;

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

		ans = max(ans, dfs(i, 1));

	}

	cout << (n-ans)<<endl;//(最长的)

	return 0;

}


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

using namespace std;

#define sci1(a) scanf("%d",&a)

#define sci2(a,b) scanf("%d %d",&a,&b)

#define sci3(a,b,c) scanf("%d %d %d",&a,&b,&c)

#define scs(s) scanf("%s",s)

#ifndef GET_MACRO



#define GET_MACRO(__1,__2,__3,NAME,...) NAME



#endif // GET_MACRO



#define sci(...) GET_MACRO(__VA_ARGS__,sci3,sci2,sci1)(__VA_ARGS__)

#define ll long long

#define pii pair<int,int>

#define mp(a,b) make_pair(a,b)

#define LSB(i) ((i)&(-i))

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

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

#define infl 0x7ffffffffffffff

#define infi  0x7fffffff

#define fill_(a,b) fill(a.begin(),a.end(),b)

#define pb push_back

#define xx first

#define yy second

int main(){

    int n,i,tmp;

    sci(n);

    vector<int> vct(n+1,-1);

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

        sci(tmp);

        if(vct[tmp-1]==-1){

            vct[tmp]=1;

        }

        else{

            vct[tmp]=vct[tmp-1]+1;

        }

    }

    cout<<n-*max_element(vct.begin(),vct.end())<<endl;

}
// Slower C++ solution:


#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

int a[200005];

map<int, int>m;// [200005];//就相当于是int m[200005];

vector<int> g[200005];

int vis[200005]={0};

int maxn = 0;

int dfs(int i, int ans) {

	if(vis[i]!=0)return ans;

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

	{

		//if(!vis[i])

		ans = max(dfs(g[i][j], ans) + 1, ans);

	}

	vis[i]=ans;

	return ans;

}

int main() {

	int n; cin >> n;

	int x;

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

		cin >> x;

		m[x] = i;

	}

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

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

			//如果 i+1的下标比i要大, 就是在他后面

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

	}

	//建图完毕

	int ans = 0;

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

		ans = max(ans, dfs(i, 1));

	}

	cout << (n-ans)<<endl;//(最长的)

	return 0;

}


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

using namespace std;

#define INF 2000000000

typedef long long int ll;

typedef pair<ll,ll> ii;

typedef pair<ii,ll> iii;

typedef vector<ll> vi;

typedef vector<ii> vii;

#define getbit(n,i) (((n)&(1LL<<(i)))!=0)

#define setbit0(n,i) ((n)&(~(1LL<<(i))))

#define setbit1(n,i) ((n)|(1LL<<(i)))

#define lastone(n) ((n)&(-(n)))

#define read freopen("debug\\in.txt","r",stdin)

#define write freopen("debug\\out.txt","w",stdout)

#define DBG(a) cout<<#a<<" ->->->-> "<<a<<"\n"

#define EN cout<<"\n"

#define fi first

#define se second

#define PI (acos(-1))

#define fastread ios::sync_with_stdio(false);cin.tie(NULL)

#define mod (1000000007)

#define asz 200005

template<class T> ostream& operator<<(ostream &s,pair<T,ll> a)

{

    s<<a.fi<<' '<<a.se;

    return s;

}

int main()

{

    fastread;

    ll T=1;

//    cin>>T;

    for(ll qq=1;qq<=T; qq++)

    {

        ll n;

        cin>>n;

        vii v(n);

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

        {

            cin>>v[i].fi;

            v[i].se=i;

        }

        sort(v.begin(),v.end());

        ll ans=1;

        ll l=0;

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

        {

            if(v[i].se<v[i-1].se)ans=max(ans,i-l),l=i;

        }

        ans=max(ans,n-l);

        cout<<n-ans<<endl;

    }

}
// Slower C++ solution:


#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

int a[200005];

map<int, int>m;// [200005];//就相当于是int m[200005];

vector<int> g[200005];

int vis[200005]={0};

int maxn = 0;

int dfs(int i, int ans) {

	if(vis[i]!=0)return ans;

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

	{

		//if(!vis[i])

		ans = max(dfs(g[i][j], ans) + 1, ans);

	}

	vis[i]=ans;

	return ans;

}

int main() {

	int n; cin >> n;

	int x;

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

		cin >> x;

		m[x] = i;

	}

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

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

			//如果 i+1的下标比i要大, 就是在他后面

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

	}

	//建图完毕

	int ans = 0;

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

		ans = max(ans, dfs(i, 1));

	}

	cout << (n-ans)<<endl;//(最长的)

	return 0;

}


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

#define ll          long long int

#define uu          first

#define vv          second

#define pii         pair<int,int>

#define pll         pair<ll,ll>

#define INF         1e9

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

using namespace std;



const int MAX = 1e6 + 6;

int main()

{

    fastRead;

    int n;

    cin>>n;

    vector<int>pos(n+1);

    

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

        int tmp;

        cin>>tmp;

        pos[tmp] = i;

    }

    

    int last = 0 , ans = 0 , cnt = 0;

    

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

        

        if(pos[i] > last) {

            cnt++;

            ans = max(ans , cnt);

        }

        else cnt = 1;

        last = pos[i];

    }

    cout<<n-ans<<'\n';

    return 0;

    

    

}
// Slower C++ solution:


#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

int a[200005];

map<int, int>m;// [200005];//就相当于是int m[200005];

vector<int> g[200005];

int vis[200005]={0};

int maxn = 0;

int dfs(int i, int ans) {

	if(vis[i]!=0)return ans;

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

	{

		//if(!vis[i])

		ans = max(dfs(g[i][j], ans) + 1, ans);

	}

	vis[i]=ans;

	return ans;

}

int main() {

	int n; cin >> n;

	int x;

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

		cin >> x;

		m[x] = i;

	}

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

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

			//如果 i+1的下标比i要大, 就是在他后面

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

	}

	//建图完毕

	int ans = 0;

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

		ans = max(ans, dfs(i, 1));

	}

	cout << (n-ans)<<endl;//(最长的)

	return 0;

}


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

#include <cstdio>

#define fastio {ios_base::sync_with_stdio(false); cin.tie(NULL);}

#define nln cout << '\n'

#define ll long long int

#define INF (ll)1e+12

#define MAX 300100

#define mp(i, j) make_pair(i, j)

#define here cout  << "here";nln;

#define mul(a, b, mod) (((a % mod) * (b % mod)) % mod)

#define add(a, b, mod) (((a % mod) + (b % mod)) % mod)

#define inf 100000

#define M 1000000000LL



using namespace std;



ll a[200100];



int main()

{

    ll n, l, k, i, ans, cnt, x;



    cin >> n;

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

        cin >> x;

        a[x] = i;

    }



    cnt = 1;

    ans = n;

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

        if(a[i] < a[i-1]){

           ans = min(n-cnt, ans);

           cnt = 0;

        }

        cnt++;

    }



    ans = min(n-cnt, ans);



    cout << ans << endl;

}
// Slower C++ solution:


#include<iostream>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

int a[200005];

map<int, int>m;// [200005];//就相当于是int m[200005];

vector<int> g[200005];

int vis[200005]={0};

int maxn = 0;

int dfs(int i, int ans) {

	if(vis[i]!=0)return ans;

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

	{

		//if(!vis[i])

		ans = max(dfs(g[i][j], ans) + 1, ans);

	}

	vis[i]=ans;

	return ans;

}

int main() {

	int n; cin >> n;

	int x;

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

		cin >> x;

		m[x] = i;

	}

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

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

			//如果 i+1的下标比i要大, 就是在他后面

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

	}

	//建图完毕

	int ans = 0;

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

		ans = max(ans, dfs(i, 1));

	}

	cout << (n-ans)<<endl;//(最长的)

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 6.565341194751498x):
///in the name of Allah the most beneficent the most merciful.

#include<bits/stdc++.h>

#define ll long long

#define pb push_back

#define MAX 1e18

#define MIN -1e18

#define MOD 998244353

//#define mod2 20071027

//#define MOD 998244353

#define rep(i,a) for(int i=0;i<a;i++)

#define rep1(i,a) for(int i=1;i<=a;i++)

#define base 139

//#define mod 1000074259

#define base2 31

#define memz(a) memset(a, 0, sizeof(a))

#define memn(a) memset(a, -1, sizeof(a))

#define in1(a) scanf("%lld", &a)

#define in2(a, b) scanf("%lld%lld", &a, &b)

#define TC(c) printf("Case #%lld: ", ++c)

#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);

using namespace std;

const ll N=300010, M=1000005;

ll n, a[N],pos[N],sz[N],vis[N], res;



int main()

{

    in1(n);

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

    {

        in1(a[i]);

        pos[a[i]]=i;

    }

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

    {

        if(vis[a[i]]==0)

        {

            vis[a[i]]=1;

            sz[a[i]]++;

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

            {

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

                    break;

                vis[j]=1;

                sz[a[i]]++;

            }

            res=max(res, sz[a[i]]);

        }

    }

    printf("%lld\n",n-res);

    return 0;

}

/*



*/