stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<iostream>

#include<string>

#include<algorithm>

#include<cstdlib>

template<typename T>

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



int main() {

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

  std::string s; std::cin >> s;

  int ans = s.size();

  int aa[] = {0, 1, 0, 1};

  int bb[] = {0, -1, -1, 0};

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

    int a = aa[i], b = bb[i];

    int cur = a-b;

    for(auto c: s) {

      if(c=='0')      { --a; --b; }

      else if(c=='1') { ++a; ++b; }

      else            { --a; ++b; }

      if(a < 0) a += 2;

      if(b > 0) b -= 2;

      cur = std::max(cur, a-b);

    }

    ans = std::min(ans, cur);

  }

  fin(ans);

  return 0;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<string>

#include<algorithm>

#include<cstdlib>

template<typename T>

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



int main() {

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

  std::string s; std::cin >> s;

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

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

  for(int i = 0; i < s.size(); i += 2) {

    char c = s[i];

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

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

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

    if(a0 < 0) a0 += 2;

    if(b0 > 0) b0 -= 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);

    c = s[i+1];

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

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

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

    if(a1 < 0) a1 += 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);

  }

  if(s.size()%2==1) {

    char c = s.back();

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

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

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

    if(a0 < 0) a0 += 2;

    if(b0 > 0) b0 -= 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;

}




// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}






// Fastest known solution for this problem:
// Original C++ solution (slower):
#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";

}

// Optimized solution to the same problem (faster):
#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";

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
//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);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
//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);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

 } 

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem: