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

#include<cstdio>

#include<cstring>

using namespace std;

int a[200000+50],bj[200000+50];

int main ()

{

	int n,i;

	while(scanf("%d",&n)!=EOF)

	{	

		memset(bj,0,sizeof(bj));

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

			cin>>a[i];

		int mx=-1;

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

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

		cout<<n-mx<<endl;

	}

	return 0;

 } 

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

using namespace std;



const int N = 2e5+7;

int dp[N];



int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);



    int n;

    cin>>n;



    int ans = 0;

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

        int x;

        cin>>x;

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

        ans = max(ans, dp[x]);

    }

    cout<<n-ans<<endl;

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

#include<cstdio>

#include<cstring>

using namespace std;

int a[200000+50],bj[200000+50];

int main ()

{

	int n,i;

	while(scanf("%d",&n)!=EOF)

	{	

		memset(bj,0,sizeof(bj));

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

			cin>>a[i];

		int mx=-1;

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

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

		cout<<n-mx<<endl;

	}

	return 0;

 } 

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

using namespace std;

using ll = long long;



void solve() {

    int n;

    cin >> n;

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

    for(int i=0;i<n;i++) cin >> v[i];

    set<int> s;

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

        auto it = s.find(v[i]-1);

        if(it==s.end()) {

            dp[v[i]]=1;

        } else {

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

        }

        s.insert(v[i]);

    }



    int x = *max_element(dp.begin(),dp.end());

    cout << n-x << "\n";



}



int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);



    solve();

    return 0;

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

#include<cstdio>

#include<cstring>

using namespace std;

int a[200000+50],bj[200000+50];

int main ()

{

	int n,i;

	while(scanf("%d",&n)!=EOF)

	{	

		memset(bj,0,sizeof(bj));

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

			cin>>a[i];

		int mx=-1;

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

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

		cout<<n-mx<<endl;

	}

	return 0;

 } 

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

#define FLASH ios_base::sync_with_stdio(0);

#define ll long long

#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;

#define deb(x)cout<<"#x = "<<(x)<<endl;

#define pb push_back

#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define endl "\n"

#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";

#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";





using namespace std;



ll massiv[200010];

ll dp[200010];

ll n;



int main(){

FLASH;

cin>>n;

ll maxx=0;

for(ll i=1;i<=n;i++)cin>>massiv[i];

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

{

  dp[massiv[i]]=max(dp[massiv[i]-1]+1,dp[massiv[i]]);

  maxx=max(maxx,dp[massiv[i]]);  	

}



cout<<n-maxx<<endl;













return 0;

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

using namespace std;

int main(void){

    int n,q[200008]={0},m=0;

    cin>>n;

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

        int p;

        cin>>p;

        if(q[p-1]==0){

            q[p]=1;

        }else{

            q[p]=q[p-1]+1;

        }

    }

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

        m=max(m,q[i+1]);

    }

    cout<<n-m<<endl;

}


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

#include <vector>

using namespace std;

int main(void){

    int n;

    cin >> n;

    vector<int> p(n, 0), pos(n, 0);

    for(int i=0;i<n;i++) cin >> p[i];

    for(int i=0;i<n;i++) pos[--p[i]] = i;

    

    int ans = 1, str = 1;

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

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

        else str = 1;

        if(ans < str) ans = str;

    }

    cout << n-ans << endl;

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

using namespace std;

typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

 

/* attention

    long longのシフト演算には気をつけよう

    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも

    sizeは(int)とキャストしよう

    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？

*/



int main(){

    int N; cin >> N;

    int dp[201010] = {};

    int p[201010] = {};

    for(int i=1; i<=N; ++i) cin >> p[i];



    int maxv = 0;

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

        int c = p[i];

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

        chmax(maxv, dp[c]);

    }



    cout << N-maxv << endl;

}

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

using namespace std;

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

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

#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)

#define reprev(i,n) reprrev(i,0,n)

typedef long long ll;

typedef unsigned long long ull;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }



/* attention

    long longのシフト演算には気をつけよう

    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも

    sizeは(int)とキャストしよう

    cin.tie(0);

    ios::sync_with_stdio(false);<- これら、printfとかと併用しない方が良さそう



*/



const ll mod = 1e9+7;



void chmod(ll &M){

    if(M >= mod) M %= mod;

    else if(M < 0){

        M += (abs(M)/mod + 1)*mod;

        M %= mod;

    }

}



ll modpow(ll x, ll n){

    if(n==0) return 1;

    ll res=modpow(x, n/2);



    if(n%2==0) return res*res%mod;

    else return res*res%mod*x%mod;

}



int getl(int i, int N) { return i==0? N-1:i-1; };

int getr(int i, int N) { return i==N-1? 0:i+1; };



/* <--------------------------------------------> */



typedef tuple<int, int, int> T;

// get<K>(tuple型の変数)





int main(void){

    cin.tie(nullptr);

    ios::sync_with_stdio(false);

    

    int n; cin >> n;

    vector<int> p(n);

    rep(i, n) cin >> p[i], --p[i];



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

    rep(i, n){

        if(p[i]==0) dp[p[i]]=1;

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

    }

    int Mv=0;

    rep(i, n) chmax(Mv, dp[i]);

    cout << n-Mv << endl;



    return 0;

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

using namespace std;

typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

 

/* attention

    long longのシフト演算には気をつけよう

    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも

    sizeは(int)とキャストしよう

    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？

*/



int main(){

    int N; cin >> N;

    int dp[201010] = {};

    int p[201010] = {};

    for(int i=1; i<=N; ++i) cin >> p[i];



    int maxv = 0;

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

        int c = p[i];

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

        chmax(maxv, dp[c]);

    }



    cout << N-maxv << endl;

}

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

using namespace std;

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

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

#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)

#define reprev(i,n) reprrev(i,0,n)

typedef long long ll;

typedef unsigned long long ull;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }



const ll mod = 1e9+7;





void chmod(ll &M){

    if(M >= mod) M %= mod;

    else if(M < 0){

        M += (abs(M)/mod + 1)*mod;

        M %= mod;

    }

}



ll modpow(ll x, ll n){

    if(n==0) return 1;

    ll res=modpow(x, n/2);



    if(n%2==0) return res*res%mod;

    else return res*res%mod*x%mod;

}



int getl(int i, int N) { return i==0? N-1:i-1; };

int getr(int i, int N) { return i==N-1? 0:i+1; };



// 線分 ab の偏角 返り値は[-π, π]

double argument(const pair<double, double> &a, const pair<double, double> &b){

    double ax=a.first, ay=a.second, bx=b.first, by=b.second;

    return atan2(by-ay, bx-ax);

}



/* <-----------------------------------------------------------------------------------> */

/* <-----------------------------------------------------------------------------------> */

/* <-----------------------------------------------------------------------------------> */

/* <-----------------------------------------------------------------------------------> */

/* <-----------------------------------------------------------------------------------> */

/* <-----------------------------------------------------------------------------------> */

/* <-----------------------------------------------------------------------------------> */

/* <-----------------------------------------------------------------------------------> */



/* 注意 



    1LL<<60 * N とかのオーバーフローに気を付けろ

    制約がヒントになる、ちゃんと全ての制約を見ろ



*/



int main(void) {

    cin.tie(0);

    ios::sync_with_stdio(false);



    int n; std::cin >> n;

    std::vector<int> p(n);

    rep(i, n) cin >> p[i];

    std::vector<int> dp(n+1, 0);

    int ans = 0;

    rep(i, n) { dp[p[i]] = dp[p[i]-1]+1; ans = std::max(ans, dp[p[i]]); }

    std::cout << n-ans << std::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.312679597273777x):
#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;

		}

	}

	// cnt=1;

	// for(int i=n-1;i;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 <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.3591183073952715x):
#include <bits/stdc++.h>

#define LL long long

#define db double

using namespace std;



const int MAXN = 200200;

const int INF = 0x3f3f3f3f;



template <typename T> inline void read(T &x) {

	char c = getchar();

	bool f = false;

	for (x = 0; !isdigit(c); c = getchar()) {

		if (c == '-') {

			f = true;

		}

	}

	for (; isdigit(c); c = getchar()) {

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

	}

	if (f) {

		x = -x;

	}

}



template <typename T> inline bool CheckMax(T &a, const T &b) {

	return a < b ? a = b, true : false;

}



template <typename T> inline bool CheckMin(T &a, const T &b) {

	return a > b ? a = b, true : false;

}



int n, a[MAXN];

int cnt;

#define ls lower_bound

#define us upper_bound



signed main() {

	read(n);

	for(int i = 1, x; i <= n; i++) read(x), a[x] = i;

	int ans = 0;

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

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

			CheckMax(ans, ++len);

		}

		else len = 1;

	}

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

	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: 22.510213039194372x):
#include <cstdio>

#include <algorithm>

using namespace std;



const int MAXN = 200005;

int p[MAXN], ord[MAXN];



int main()

{

	int n;

	scanf("%d", &n);

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

	{

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

		ord[p[i]] = i;

	}

	int ans = 0, len = 1;

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

		if (ord[i] >= ord[i-1]) len++;

		else ans = max(ans, len), len = 1;

	ans = max(ans, len);

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

	return 0;

}
// Slower C++ solution:
#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;

		}

	}

	// cnt=1;

	// for(int i=n-1;i;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;

}


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

#include <algorithm>

using namespace std;



const int MAXN = 200005;

int p[MAXN], ord[MAXN];



int main()

{

	int n;

	scanf("%d", &n);

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

	{

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

		ord[p[i]] = i;

	}

	int ans = 0, len = 1;

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

		if (ord[i] >= ord[i-1]) len++;

		else ans = max(ans, len), len = 1;

	ans = max(ans, len);

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

	return 0;

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

#define LL long long

#define db double

using namespace std;



const int MAXN = 200200;

const int INF = 0x3f3f3f3f;



template <typename T> inline void read(T &x) {

	char c = getchar();

	bool f = false;

	for (x = 0; !isdigit(c); c = getchar()) {

		if (c == '-') {

			f = true;

		}

	}

	for (; isdigit(c); c = getchar()) {

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

	}

	if (f) {

		x = -x;

	}

}



template <typename T> inline bool CheckMax(T &a, const T &b) {

	return a < b ? a = b, true : false;

}



template <typename T> inline bool CheckMin(T &a, const T &b) {

	return a > b ? a = b, true : false;

}



int n, a[MAXN];

int cnt;

#define ls lower_bound

#define us upper_bound



signed main() {

	read(n);

	for(int i = 1, x; i <= n; i++) read(x), a[x] = i;

	int ans = 0;

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

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

			CheckMax(ans, ++len);

		}

		else len = 1;

	}

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

	return 0;

}

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

#include <algorithm>

using namespace std;



const int MAXN = 200005;

int p[MAXN], ord[MAXN];



int main()

{

	int n;

	scanf("%d", &n);

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

	{

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

		ord[p[i]] = i;

	}

	int ans = 0, len = 1;

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

		if (ord[i] >= ord[i-1]) len++;

		else ans = max(ans, len), len = 1;

	ans = max(ans, len);

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

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

#define maxn 200005

using namespace std;

inline int read(){

	int x=0,f=1;char c=getchar();

	while(c<'0'||c>'9'){

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

		c=getchar();

	}

	while(c>='0'&&c<='9'){

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

		c=getchar();

	}

	return x*f;

}

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

int main(){

	n=read();

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

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

		f[a[i]]=f[a[i]-1]+1;//求最长连续子序列 

	}

	int ans=0;

	for(int i=1;i<=n;i++) if(f[i]>ans) ans=f[i];

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

	

	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.299215894287031x):
#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=1;i<=n;i++)

    {

        if(a[i]==1)

        {

            ans=max(ans,b[1]);

        }

        else 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;

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



using namespace std;



int a[200001], n,f[200001],ans;

bool b[200001];

int jShu;



int main(){

	cin>>n;

	for(int i=1; i<=n; i++) cin>>a[i],f[i]=1;

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

	{

		b[a[i]]=true;

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

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

	}



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

#include<cstdio>

#include<queue>

#include<algorithm>

#include<cmath>

#include<ctime>

#include<set>

#include<map>

#include<stack>

#include<cstring>

#define inf 2147483647

#define ls rt<<1

#define rs rt<<1|1

#define lson ls,nl,mid,l,r

#define rson rs,mid+1,nr,l,r

#define N 1000010

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

#define p(a) putchar(a)

#define g() getchar()



using namespace std;

int n;

int a[N],b[N];

int ans=1;

void in(int &x){

    int y=1;

    char c=g();x=0;

    while(c<'0'||c>'9'){

        if(c=='-')y=-1;

        c=g();

    }

    while(c<='9'&&c>='0'){

        x=(x<<1)+(x<<3)+c-'0';c=g();

    }

    x*=y;

}

void o(int x){

    if(x<0){

        p('-');

        x=-x;

    }

    if(x>9)o(x/10);

    p(x%10+'0');

}

int main(){

    in(n);

    For(i,1,n)

    	in(a[i]);

    b[a[1]]=1;

    For(i,2,n){

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

    	ans=max(ans,b[a[i]]);

    }

    o(n-ans);

    return 0;

}