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

#include<algorithm>

#include<cstdlib>

template<typename T>

void fin(T const& t){ std::cout << t << std::endl; exit(0); }

char buf[1000010]; 

int main() {

  std::cin.tie(0); std::ios::sync_with_stdio(false);

  std::cin >> buf;

  int a0 = 0, a1 = 1, b0 = 0, b1 = -1;

  int c0 = a0-b0, c1 = a0-b1, c2 = a1-b0, c3 = a1-b1;

  for(char *p = buf; *p; p++) {

    if(*p=='0')      { --a0; --a1; --b0; --b1; }

    else if(*p=='1') { ++a0; ++a1; ++b0; ++b1; }

    else             { --a0; --a1; ++b0; ++b1; }

    if(a0 < 0) a0 += 2;

    if(a1 < 0) a1 += 2;

    if(b0 > 0) b0 -= 2;

    if(b1 > 0) b1 -= 2;

    c0 = std::max(c0, a0-b0);

    c1 = std::max(c1, a0-b1);

    c2 = std::max(c2, a1-b0);

    c3 = std::max(c3, a1-b1);

  }

  fin(std::min(std::min(c0, c1), std::min(c2, c3)));

  return 0;

}


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

#include<algorithm>

char buf[1000010];

int main() {

  scanf("%s", buf);

  int a0 = 0, a1 = 1, b0 = 0, b1 = -1;

  int c0 = a0-b0, c1 = a0-b1, c2 = a1-b0, c3 = a1-b1;

  for(char *p = buf; *p; p++) {

    if(*p=='0')      { --a0; --a1; --b0; --b1; }

    else if(*p=='1') { ++a0; ++a1; ++b0; ++b1; }

    else             { --a0; --a1; ++b0; ++b1; }

    if(a0 < 0) a0 += 2;

    if(a1 < 0) a1 += 2;

    if(b0 > 0) b0 -= 2; 

    if(b1 > 0) b1 -= 2; 

    if(c0 < a0-b0) c0 = a0-b0;

    if(c1 < a0-b1) c1 = a0-b1;

    if(c2 < a1-b0) c2 = a1-b0;

    if(c3 < a1-b1) c3 = a1-b1;

  }

  if(c0 > c1) c0 = c1;

  if(c2 > c3) c2 = c3;

  if(c0 > c2) c0 = c2;

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

  return 0;

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

#include<cstdio>

#include<algorithm>

#include<vector>

#include<utility>

#include<cmath>

#include<string>

#include<cstring>

#include<map>

#include<queue>

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

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

#define prin(arg) std::cout<<arg<<"\n"

#define prin2(arg1,arg2) std::cout<<arg1<<" "<<arg2<<"\n"

#define fill(arg,n) std::memset(arg,n,sizeof(arg))

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

using std::cin;

typedef long long ll;

typedef std::pair<int,int> pi;

typedef std::pair<ll,int> pli;

typedef std::vector<int> vi;

typedef std::string str;

const int INF=1e+9;

const ll INFLL=1e+17;

const ll MOD=1e+9+7;

int N,M;

int B[100010];

ll A[100010],C[100010];

bool comp(pli& a,pli& b){

  return a.first>b.first;

}

int main(){

  cin>>N>>M;

  rep(i,N) cin>>A[i];

  rep(i,M){

    cin>>B[i]>>C[i];

  }

  pli p[100010];

  rep(i,M){

    p[i]=mp(C[i],B[i]);

  }

  std::sort(A,A+N);

  std::sort(p,p+M,comp);

  int j=0;

  rep(i,M){

    int b=p[i].second,c=p[i].first;

    rep(k,b){

      if(A[j]<c){

	A[j]=c;

	j++;

      }

      else{

	ll res=0;

	rep(i,N){

	  res+=A[i];

	}

	prin(res);

	return 0;

      }

    }

  }

  ll res=0;

  rep(i,N){

    res+=A[i];

  }

  prin(res);

  return 0;

}


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

#include <algorithm>

#include <vector>

#include <string>

#include <utility>

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

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

#define F first

#define S second

using namespace std;

template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }

using ll = long long;

using pi = pair<int,int>;

using pl = pair<ll,ll>;

int main()

{

  ll n,m; cin >> n >> m;

  vector<ll> a(n);

  vector<ll> b(m),c(m);

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

  rep(i,m) cin >> b[i] >> c[i];



  vector<pl> v;

  rep(i,n) {

    v.push_back({a[i], 1});

  }

  rep(i,m) {

    v.push_back({c[i], b[i]});    

  }



  sort(v.begin(), v.end(), [](pl x, pl y){

			     return x.F > y.F;

			   });

  int idx = 0;

  ll res = 0;

  while(n-- > 0) {

    if(v[idx].S > 0) {

      res += v[idx].F;

      v[idx].S--;

    }

    else {

      idx++;

      res += v[idx].F;

      v[idx].S--;      

    }

  }

  cout << res << "\n";

  

  return 0;

}
// Slower C++ solution:
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

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

typedef long long ll;

using namespace std;

const int N = 1e5 + 5;

int main() {

    abdelrahman010

    multiset<int> st;

    int n , m , a[N];

    pair<int , int> b[N];

    cin >> n >> m;

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

        cin >> a[i] , st.insert(a[i]);

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

        cin >> b[i].second >> b[i].first;

    sort(b , b + m , greater<>());

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

        while(*st.begin() < b[i].first && b[i].second) {

            b[i].second--;

            st.erase(st.begin());

            st.insert(b[i].first);

        }

    }

    ll ans = 0;

    for(auto &i : st)

        ans += i;

    cout << ans;

    return 0;

}

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

using namespace std;

const int maxn = 3e5 + 123;

#define int long long 

int n, m;

pair <int, int> a[maxn];

string s, t;

main () { 

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    cin >> n >> m;   

    multiset <int> q;

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

    	int x;

    	cin >>x;

    	q.insert(x);

    }



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

    	cin >> a[i].second >> a[i].first;

    }



    sort(a + 1, a + m + 1);

    reverse(a + 1, a + m + 1);



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

    	while(*q.begin() < a[i].first && a[i].second){

    		int x = *q.begin();

    		q.erase(q.find(x));

    		q.insert(a[i].first);

    		a[i].second--;

    	}

    }

    int ans = 0;

    while(q.size()) {

    	int x = *q.begin();

    	ans += x;

    	q.erase(q.find(x));

    }

    cout <<ans;

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

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

const int inf = 1e9;

const ll INF = 1e18;

const double pi = 3.14159265358979323846;

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

using Graph = vector<vector<int>>;

using pint = pair<int, int>;

int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };

int dxx[8] = { 1, 1, 1, 0, 0, -1, -1, -1 }, dyy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };



int main() {

    int n, m;

    cin >> n >> m;

    pair<ll, ll> p[200005];

    ll l;

    vector<ll> a (n), b (m), c (m);

    rep (i, n) {

        cin >> p[i].first;

        p[i].second = 1;

        l++;

    }

    rep (i, m) {

        cin >> p[n + i].second >> p[n + i].first;

        l += p[n + i].first;

    }

    sort (p, p + n + m, greater<pair<ll, ll>>());

    ll ans = 0, now = n;

    rep (i, n) {

        if (now > p[i].second) {

            ans += p[i].first * p[i].second;

            now -= p[i].second;

        } else {

            ans += p[i].first * now;

            break;

        }

    }

    cout << ans << "\n";

}

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

using namespace std;

typedef long long ll;

const ll inf = 1e18;

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

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

#define int ll

using pint = pair<int, int>;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};



signed main() {

    int n, m;

    cin >> n >> m;

    vector<int> vec;

    rep (i, 0, n) {

        int a;

        cin >> a;

        vec.push_back (a);

    }

    sort (vec.begin(), vec.end(), greater<int>());

    pint bc[m];

    rep (i, 0, m) { cin >> bc[i].second >> bc[i].first; }

    sort (bc, bc + m, greater<pint>());

    int cnt = 0;

    int i = 0, j = 0;

    int ans = 0;

    while (cnt < n) {

        if (i < n && j < m) {



            if (vec[i] > bc[j].first) {

                ans += vec[i];

                i++;

                cnt++;

            } else {

                if (n - cnt > bc[j].second) {

                    ans += bc[j].second * bc[j].first;

                    cnt += bc[j].second;

                    j++;

                } else {

                    ans += bc[j].first * (n - cnt);

                    j++;

                    cnt = n;

                }

            }

        } else if (i < n) {

            ans += vec[i];

            i++;

            cnt++;

        } else {

            if (n - cnt > bc[j].second) {

                ans += bc[j].second * bc[j].first;

                cnt += bc[j].second;

                j++;

            } else {

                ans += bc[j].first * (n - cnt);

                j++;

                cnt = n;

            }

        }

        // cout << i << " " << j << " " << cnt << "\n";

    }

    cout << ans << "\n";

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

using namespace std;

typedef long long ll;

#define traverse(container,it)  for(auto it = container.begin();it != container.end(); it++)

int main()

{

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

    int n,m;

    ll sum = 0;

    multiset< int >  number;

    priority_queue< pair< int,int > > spare;



    cin >> n >> m;



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

        int x;

        cin >> x;

        number.insert(x);

    }



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

        int a,b;

        cin >> a >> b;

        spare.push(make_pair(b,a));

    }



    multiset< int >::iterator it = number.begin();



    while(!spare.empty() && it != number.end()){

        pair< int,int > curr = spare.top();



        while((curr.first> *it) && curr.second>0 && (it != number.end())){

            curr.second--;

            sum += curr.first;

            it++;

        }



        if(curr.first <= *it) break;



        spare.pop();

    }



    while(it != number.end()){

        sum += *it;

        it++;

    }



    cout << sum << endl;



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 4.35358732654812x):
//NOT MY CODE

#include <limits.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>



int comp(const void *a, const void *b){return *(int*)b-*(int*)a;}



int main(void){

	int n, m, i;

	int x[200000][2];

	scanf("%d%d", &n, &m);

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

		int A;

		scanf("%d", &A);

		x[i][0]=A;

		x[i][1]=1;

	}

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

		int B, C;

		scanf("%d%d", &B, &C);

		x[i][0]=C;

		x[i][1]=B;

	}

	qsort(x, n+m, sizeof(int)*2, comp);

	int j=n;

	long sum=0;

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

		if(x[i][1]<j){

			sum += ((long)x[i][0])*x[i][1];

			j -= x[i][1];

		}else{

			sum += ((long)x[i][0])*j;

			break;

		}

	}

	printf("%ld\n", sum);

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

using namespace std;

typedef long long ll;

#define traverse(container,it)  for(auto it = container.begin();it != container.end(); it++)

bool comp(pair< int,int > a,pair< int,int > b){

    return a.first > b.first;

}

int main()

{

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

    int n,m,l;

    ll sum  = 0;

    cin >> n >> m;

    vector< pair< int,int > > number;

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

        int x;

        cin >> x;

        number.push_back(make_pair(x,1));

    }

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

        int a,b;

        cin >> a >> b;

        number.push_back(make_pair(b,a));

    }

    sort(number.begin(),number.end(),comp);

    l=n;

    for(auto it = number.begin(); it != number.begin()+n; it++){

        if((it->second)<l){

            sum += (ll)((ll)(it->first)*(ll)(it->second));

            l -= it->second;

        }

        else{

            sum += (ll)(it->first)*l;

            break;

        }

    }



    cout << sum << endl;



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 4.312512108934672x):
//NOT MY CODE

#include <limits.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>



int comp(const void *a, const void *b){return *(int*)b-*(int*)a;}



int main(void){

	int n, m, i;

	int x[200000][2];

	scanf("%d%d", &n, &m);

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

		int A;

		scanf("%d", &A);

		x[i][0]=A;

		x[i][1]=1;

	}

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

		int B, C;

		scanf("%d%d", &B, &C);

		x[i][0]=C;

		x[i][1]=B;

	}

	qsort(x, n+m, sizeof(int)*2, comp);

	int j=n;

	long sum=0;

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

		if(x[i][1]<j){

			sum += ((long)x[i][0])*x[i][1];

			j -= x[i][1];

		}else{

			sum += ((long)x[i][0])*j;

			break;

		}

	}

	printf("%ld\n", sum);

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

#include <cstdio>

using namespace std;

int a[300000];



int main()

{

    int n, x;

    scanf("%d", &n);

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

    {

        scanf("%d", &x);

        a[x] = i;

    }

    int maxn = 0, now = 1;

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

    {

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

            now ++;

        else

        {

            maxn = max(maxn, now);

            now = 1;

        }

    }

    maxn = max(maxn, now);

    cout << n - maxn << endl;

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



using namespace std;

int f[200005];

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





int main()

{

    scanf("%d", &n);

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

    {

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

        pos[a[i]] = i;

    }

    int len = 1;

    int ans = 0;

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

    {

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

        {

            len++;

        }

        else

        {

            ans = max(ans, len);

            len = 1;

        }

    }

    ans = max(ans, len);

    cout << n-ans << endl;



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

#include<cstdio>

using namespace std;

int f[100005*2],r[100005*2];

int a[100005*2];

bool ok[100005*2];

int maxm;

int main(){

	int n;

	scanf("%d",&n);

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

		f[i+1]=1;

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

	}

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

		ok[a[i]]=1;

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

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

		}

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

	}

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

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



using namespace std;

long long ll[200001];

int main()

{

	

	int n;

	int j;

	int ans=1;

	int m=1;

	cin >> n;

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

	{

		cin >> j;

		ll[j] = i + 1;

	}

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

	{

		m = 1;

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

		{

			

			if (ll[k] < ll[k + 1])

				m++;

			else

			{

				if (m > ans)

					ans = m;

				break;

			}



		}



	}

	cout << n - ans;



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

#include<stdio.h>

#include<math.h>

#include<string>

#include<string.h>

#include<algorithm>

using namespace std;

#define ll long long

const int maxn = 2e5+10;

int a[maxn];

int n;

int dp[maxn];

int main()

{

	scanf("%d",&n);

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

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

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

	int ans=0;

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

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

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

using namespace std;



int n;

int x,ans;

int dp[400100];

int main()

{

    cin>>n;

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

    {

        cin>>x;

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

        //cout<<" "<<dp[x]<<endl;

    }

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

    cout<<n-ans;

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

using namespace std;

const int N=2e5+9;



int a[N],t[N];



int main(){

	int n,ans=1,c=1;

	cin>>n;

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

		scanf("%d",a+i);

		t[a[i]]=i;

	}

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

		if(t[i]<t[i+1])c++;

		else c=1;

		ans=max(ans,c);

	}

	cout<<n-ans;

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

using namespace std;



int t[210000];

int main(){

	int n,a,l=1,c=1;

	cin>>n;

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

		scanf("%d",&a);

		t[a]=i;

	}

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

		if(t[i]<t[i+1])c++;

		else c=1;

		l=max(l,c);

	}

	cout<<n-l;

	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.7873081837857485x):
/*Bismillahir Rahmanir Rahim*///{

#include <bits/stdc++.h>

#include <ext/numeric>

using namespace std; using __gnu_cxx::power;

using ll = long long; using ull = unsigned long long; using ld = long double;

const ll llinf = (1ll<<61)-1;

const double eps = 1e-6, ldeps = 1e-9;

struct Dbg {

static constexpr auto &os = cout;   // replace by cerr in interactive.

template<class C> static auto dud(C *x)->decltype(os << *x, 0);

template<class C> static char dud(...);

template<class C> typename enable_if<sizeof dud<C>(0)!=1, Dbg&>::type operator<<(const C &x) { os << x; return *this; }

template<class C> Dbg &dump(C b, C e) {

    *this << "\n[";

    int cur = 0;

    for (C i = b; i!=e and cur<26; i++, cur++) *this << ", "+2*(i==b) << *i;

    return *this << ']';

}

template<class C> typename enable_if<sizeof dud<C>(0)==1, Dbg&>::type operator<<(const C &x) {

    return dump(begin(x), end(x));

}

template<class C, size_t X> typename enable_if<!is_same<C, const char>::value, Dbg&>::type operator <<(C (&x)[X]) {

    return dump(begin(x), end(x));

}

template<class B, class C> Dbg &operator <<(const pair<B, C> &x) {

    return *this << '{' << x.first << ", " << x.second << '}';

}

Dbg &operator<<(ostream&(*x)(std::ostream&)) { os << x; return *this; }

} dbg;

void err(istringstream *iss) { delete iss; }

template<class C, class... Args> void err(istringstream *iss, const C &val, const Args &... args) {

    string name; *iss >> name; if (name.back()==',') name.pop_back();

    dbg << name << " = " << val << "; ", err(iss, args...);

}

#define bug(args...) dbg << __LINE__ << ": ", err(new istringstream(#args), args), dbg << endl

#define cbug(a, args...) if (a) bug(args);

#define ASSERT(a, o, b, args...) if (!((a)o(b))) bug(a, b, ##args), assert((a)o(b));

#define sl(a) int(strlen(a))

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

int T, Q, cn;//}

const int inf = 1000000007, mxn = 200005;



int n, p[mxn], pp[mxn];



signed main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); cout.precision(11);

    cin >> n;

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

        cin >> p[i], pp[p[i]] = i;

    }



    int mx = 0;

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

        int strt = i;

        while (pp[i+1]>pp[i]) i++;

        mx = max(mx, i-strt+1);

    }

    cout << n-mx << '\n';

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

#define inf 2000000000

#define eb emplace_back

#define pb push_back

#define fi first

#define se second

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

#define rng_23 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef vector<int> vi;

typedef vector<pair<int,int>> vii;

typedef set<int> si;

typedef multiset<int> msi;

typedef map<int,int> mii;

int ara[200001],pos[200001];

int main()

{

    int i,j,k;

    int n;

    cin>>n;

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

        cin>>ara[i];

        pos[ara[i]]=i;

    }

    int mx=0;

    i=1,j=2;

    while(i<=n){

        while(pos[j]>pos[j-1] && j<=n)

            j++;

        mx=max(mx,j-i);

        i=j;

        j++;

        //cout<<i<<endl;

    }

    cout<<n-mx;

}