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

using namespace std;

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

#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)

#define chmax(a, b) a = max(a, b)

#define chmin(a, b) a = min(a, b)

#define fi first

#define se second

#define INF 1000000009

#define LLINF 1000000000000000009LL

using ll = long long;



template <typename T>

struct SegmentTree {

  int N;

  T init;

  vector<T> dat;

  SegmentTree(int n, T init) : init(init) {

    N = 1;

    while (N < n) N *= 2;

    dat.assign(2*N-1, init);

  }

  void update(int i, T x) {

    i += N - 1;

    dat[i] = x;

    while (i > 0) {

      i = (i - 1) / 2;

      dat[i] = max(dat[i*2+1], dat[i*2+2]);

    }

  }

  // a <= x < b

  T query(int a, int b) { return query(a, b, 0, 0, N); }

  T query(int a, int b, int i, int l, int r) {

    if(r <= a || b <= l) return init;

    if(a <= l && r <= b) return dat[i];

    T vl = query(a, b, i*2+1, l, (l+r)/2);

    T vr = query(a, b, i*2+2, (l+r)/2, r);

    return max(vl, vr);

  }

};



SegmentTree<int>st(200009,0);

int a[200009];

vector<int>to[200009];

int ans[200009];

map<int,int>mp;



void dfs(int v,int p=-1){

  int i=mp[a[v]];

  int temp=st.query(i,i+1);

  st.update(i,st.query(0,i)+1);

  ans[v]=st.query(0,200000);

  for(auto u:to[v]){

    if(u==p)continue;

    dfs(u,v);

  }

  st.update(i,temp);

}



int main(){

  int n;

  cin>>n;

  vector<int>b;

  rep(i,n){

    cin>>a[i];

    b.push_back(a[i]);

  }

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

  b.erase(unique(b.begin(),b.end()),b.end());

  rep(i,b.size()){

    mp[b[i]]=i;

  }

  rep(i,n-1){

    int s,t;

    cin>>s>>t;

    s--;t--;

    to[s].push_back(t);

    to[t].push_back(s);

  }

  dfs(0);

  rep(i,n){

    cout<<ans[i]<<endl;

  }

  return(0);

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

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

#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)

#define chmax(a, b) a = max(a, b)

#define chmin(a, b) a = min(a, b)

#define fi first

#define se second

#define INF 1000000009

#define LLINF 1000000000000000009LL

#define MAX_N 200009

using ll = long long;



vector<int> a;

vector<int> to[MAX_N];

int dp[MAX_N];

int ans[MAX_N];



void dfs(int v, int p=-1) {

  int i = lower_bound(dp, dp+MAX_N, a[v]) - dp;

  int old = dp[i];

  dp[i] = a[v];

  ans[v] = i;

  if (p != -1) ans[v] = max(ans[v], ans[p]);

  for (auto u : to[v]) {

    if (u == p) continue;

    dfs(u, v);

  }

  dp[i] = old;

}



int main() {

  int n;

  cin >> n;

  a = vector<int>(n);

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

  rep(i,n-1) {

    int s, t;

    cin >> s >> t;

    s--; t--;

    to[s].push_back(t);

    to[t].push_back(s);

  }

  rep(i,MAX_N) dp[i] = INF;

  dp[0] = -INF;

  dfs(0);

  rep(i,n) {

    cout << ans[i] << endl;

  }

  return(0);

}


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

#include <fstream>

#include <set>

#include <map>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <functional>

#include <algorithm>

#include <climits>

#include <cmath>

#include <iomanip>

using namespace std;

#define ll long long int

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

#define rrep(i,n) for( int i = n; i >= 0; i-- )

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000



int ans[200010];

vector<int> G[200010];

int a[200010];

int dp[200010];

int n;

void dfs(int x, int p = -1) {

    auto itr = lower_bound(dp, dp + n, a[x]);

    int tmp = *itr;

    *itr = a[x];

    ans[x] = lower_bound(dp, dp + n, INF) - dp;

    for(auto to: G[x]) {

        if(to == p) continue;

        dfs(to, x);

    }

    *itr = tmp;

}





int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    cin >> n;

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

    rep(i, n - 1) {

        int u, v;

        cin >> u >> v;

        u--; v--;

        G[u].push_back(v);

        G[v].push_back(u);

    }

    rep(i, 200010) dp[i] = INF;

    dfs(0);

    rep(i, n) {

        cout << ans[i] << endl;

    }





    return 0;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <fstream>

#include <set>

#include <map>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <functional>

#include <algorithm>

#include <climits>

#include <cmath>

#include <iomanip>

using namespace std;

#define ll long long int

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

#define rrep(i,n) for( int i = n; i >= 0; i-- )

#define REP(i,s,t) for( int i = s; i <= t; i++ )

#define RREP(i,s,t) for( int i = s; i >= t; i-- )

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define INF 2000000000

#define mod 1000000007

#define INF2 1000000000000000000



int dp[200010];

vector<int> T[200010];

int a[200010];

int ans[200010];

int N; 

void dfs(int x = 0, int p = -1) {

    auto itr = lower_bound(dp, dp + N, a[x]);

    int prev = *lower_bound(dp, dp + N, a[x]);

    *lower_bound(dp, dp + N, a[x]) = a[x];

    ans[x] = lower_bound(dp, dp + N, INF) - dp;

    for(auto to: T[x]) {

        if(to == p) continue;

        dfs(to, x);

    }

    *itr = prev;

}



int main(void)

{

    cin.tie(0);

    ios::sync_with_stdio(false);

    cin >> N;

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

    rep(i, N - 1) {

        int u, v;

        cin >> u >> v;

        u--; v--;

        T[u].push_back(v);

        T[v].push_back(u);

    }

    rep(i, N) dp[i] = INF;

    dfs(0);

    rep(i, N) {

        cout << ans[i] << endl;

    }



    return 0;

}


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

#include<cstring>

using namespace std;

int main()

{

    int n,m,k;

    while(cin>>n>>m>>k){

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

            if(i>=(m-k+1) || i<=(n+k-1))

                cout<<i<<endl;

        }

    }

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

int main()

{

    int a, b, k;

    scanf("%d%d%d",&a,&b,&k);

    int i;

    for (i = a; i <= b; i++)

    {

        if (i - a < k || b - i < k)

        {

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

         

        }

    }

    return 0;



}


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

#include<cstdio>

#include<set>

#include<map>

#include<cstring>

using namespace std;

int main()

{  int a,i,b,k,n;

   cin>>a>>b>>k;

    n=b-a+1;

    if(2*k>=n)

    {

        for(i=a;i<=b;i++)

            cout<<i<<endl;

    }

    else {



        for(i=a;i<a+k;i++)

            cout<<i<<endl;



        for(i=b-k+1;i<=b;i++)

            cout<<i<<endl;



    }





    return 0;

}




// Optimized solution to the same problem (faster):
#include <stdio.h>

int main()

{

    int a, b, k;

    scanf("%d%d%d",&a,&b,&k);

    int i;

    for (i = a; i <= b; i++)

    {

        if (i - a < k || b - i < k)

        {

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

         

        }

    }

    return 0;



}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int A[100] ;

int main()

{

    int a,b,k;

    cin >> a >> b >> k;

    if(2* k >= (b-a+1))

    {

        for(int i =a;i<=b;i++)

            cout << i << endl;

    }

    else

    {

        for(int i = a;i<=a+k-1;i++)

        {

            cout << i << endl;

        }

        for(int i = b-k+1;i<=b;i++)

        {

            cout << i << endl;

        }

    }

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

int main()

{

    int a, b, k;

    scanf("%d%d%d",&a,&b,&k);

    int i;

    for (i = a; i <= b; i++)

    {

        if (i - a < k || b - i < k)

        {

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

         

        }

    }

    return 0;



}


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

#include<cstdio>

#include<cstring>

#include<string>

#define LL long long

using namespace std;

LL a,b;

int k;

int main()

{

    scanf("%lld%lld%d",&a,&b,&k);

    if(b-a+1<=k*2){

        for(LL i=a;i<=b;i++){

            printf("%lld\n",i);

        }

    }

    else{

        for(LL i=a;i<a+k;i++){

            printf("%lld\n",i);

        }

        for(LL i=b-k+1;i<=b;i++){

            printf("%lld\n",i);

        }

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

int main()

{

    int a, b, k;

    scanf("%d%d%d",&a,&b,&k);

    int i;

    for (i = a; i <= b; i++)

    {

        if (i - a < k || b - i < k)

        {

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

         

        }

    }

    return 0;



}


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

using namespace std;

int main()

{

    long long a,b,c;

    while(cin>>a>>b>>c)

    {

        for(long long i=a;i<=b;i++)

        {

            if(i<a+c||i>b-c)

                cout<<i<<endl;

        }

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    int a,b,k,i;

    scanf("%d %d %d",&a,&b,&k);

    printf("\n");

    if(b-a >= k+k) {

    for(i=a;i<a+k;i++){

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

    }

    for(i=b-k+1;i<=b;i++){

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

    }

    }

    else {

        for(i=a;i<=b;i++){

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

        }

    }

    return 0;

}


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

#include <iostream>

#include <algorithm>

using namespace std;

int main()

{

    int p=0,q;

    long long a,b,k;

    cin>>a>>b>>k;

    q=k;

    if((b-a)/k>=2){

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

                cout<<a+p<<endl;

                p++;

            }

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

                cout<<b-q+1<<endl;

                q--;

            }



    }

    else{

        for(int i = 0;i <= b-a; i++){

            cout<<a+i<<endl;

        }

    }

  return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    int a,b,k,i;

    scanf("%d %d %d",&a,&b,&k);

    printf("\n");

    if(b-a >= k+k) {

    for(i=a;i<a+k;i++){

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

    }

    for(i=b-k+1;i<=b;i++){

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

    }

    }

    else {

        for(i=a;i<=b;i++){

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

        }

    }

    return 0;

}


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

using namespace std;

#include <set>

#include <algorithm>

int main()

{

	int a,b,k;

	cin >> a >> b >> k;

	if(b-a+1<=k)

	{

		for(int i = a;i<=b;i++)cout<<i<<endl;

	}else{

		set<int>s;

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

		{

			s.insert(i);

		}

		

		for(int j = b;j>b-k;j--)

		{

			s.insert(j);

		}

		

		for(auto & x : s)

		{

			cout << x << endl;

		}

	}

	

	return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    int a,b,k,i;

    scanf("%d %d %d",&a,&b,&k);

    printf("\n");

    if(b-a >= k+k) {

    for(i=a;i<a+k;i++){

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

    }

    for(i=b-k+1;i<=b;i++){

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

    }

    }

    else {

        for(i=a;i<=b;i++){

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

        }

    }

    return 0;

}


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

#include<string>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<set>

#include<map>

#include<vector>

#include<queue>

#include<sstream>

using namespace std;

 

#define sf scanf

#define pf printf

#define pfn printf("\n");

#define pfk printf(" ");

#define pf0 printf("0");

#define pf1 printf("1");

#define ll long long

#define sfd(n) scanf("%d",&n);

#define sfdd(n,m) scanf("%d%d",&n,&m);

#define sfld(n) scanf("%lld",&n);

#define sfldd(n,m) scanf("%lld%lld",&n,&m);

#define sflf(n) scanf("%lf",&n);

#define sflff(n,m) scanf("%lf%lf",&n,&m);

#define sfc(n) scanf("%c",n);

#define sfcc(n,m) scanf("%c%c",n,m);

#define sfs(n) scanf("%s",n);

#define sfss(n,m) scanf("%s%s",n,m);

#define pfd(n) printf("%d",n);

#define pfld(n) printf("%lld",n);

#define pflf(n) printf("%lf",n);

#define pfc(n) printf("%c",n);

#define pfs(n) printf("%s",n);

 

#define csh(a,n) memset(a,n,sizeof(a));



int main(){

	int a,b,k;

	cin>>a>>b>>k;

	if(b-a+1>2*k){

		for(int i=a;i<a+k;i++){

			cout<<i<<endl;

		}

		for(int i=b-k+1;i<=b;i++){

			cout<<i<<endl;

		}

	}

	else{

		for(int i=a;i<=b;i++){

			cout<<i<<endl;

		}

	}

} 

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    int a,b,k,i;

    scanf("%d %d %d",&a,&b,&k);

    printf("\n");

    if(b-a >= k+k) {

    for(i=a;i<a+k;i++){

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

    }

    for(i=b-k+1;i<=b;i++){

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

    }

    }

    else {

        for(i=a;i<=b;i++){

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

        }

    }

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;

typedef long long ll;

const int MAXN = 2e3 + 5;

int a[MAXN];

set<int> s;



int main() {

    int a, b, n;

    cin >> a >> b >> n;

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

        s.insert(i);

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

        s.insert(i);

    for (auto i : s) {

        if (i >= a && i <= b)

            cout << i << endl;

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

int main()

{

    int a,b,k,i;

    scanf("%d %d %d",&a,&b,&k);

    printf("\n");

    if(b-a >= k+k) {

    for(i=a;i<a+k;i++){

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

    }

    for(i=b-k+1;i<=b;i++){

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

    }

    }

    else {

        for(i=a;i<=b;i++){

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

        }

    }

    return 0;

}


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

#include <cstdio>  

#include <cstring>  

#include <algorithm>  

  

using namespace std;  

const int maxn=2e5+100;  

int par[maxn],sum[maxn];  

int N,K,p,tot;  

  

void init(int n)  

{  

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

        par[i]=i;  

}  

  

int find(int x)  

{  

    if(par[x]==x)  

        return x;  

    return par[x]=find(par[x]);  

}  

void unit(int x,int y)  

{  

    int fx=find(x),fy=find(y);  

    if(fx!=fy)  

        par[fx]=fy;  

}  

bool same(int x,int y)  

{  

    return find(x)==find(y);  

}  

int main()  

{  

    while(~scanf("%d%d",&N,&K))  

    {  

        int ans=0;  

        memset(sum,0,sizeof(sum));  

        memset(par,0,sizeof(par));  

        tot=0;  

        init(N);  

        int t;  

        scanf("%d",&t);  

        sum[t]++;  

        p=t;  

        tot++;  

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

        {  

            scanf("%d",&t);  

            sum[t]++;  

            if(!same(t,p))  

            {  

                tot++;  

                unit(t,p);  

            }  

        }  

        sort(sum,sum+N+1);  

        if(tot<=K)  

            ans=0;  

        else  

        {  

            int cnt=tot-K;  

            int pos=lower_bound(sum,sum+N+1,1)-sum;  

            while(cnt--)  

                ans+=sum[pos++];         

        }  

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

    }  

    return 0;  

}  

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;



int n,k,a,maxa,c[200001],ans;



int main(){

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

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

        scanf("%d",&a);

        if(a>maxa)maxa=a;

        c[a]++;

    }

    n=maxa;

    sort(&c[1],&c[n+1]);

    for(int i=1;i<=n-k;i++)ans+=c[i];

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

    return 0;

}


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

#include<algorithm>

#include<map>

using namespace std;



int a[200005];

map<int,int>Q;



int main(){

	int now=0;

	int n,k;

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

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

		int x;

		scanf("%d",&x);

		a[x]++;

		if(!Q.count(x)){

			Q[x]=1;

			now++;

		}

	}

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

	int ans=0;

	for(register int i=n-now+1;i<=n-k;i++){

		ans+=a[i];

	}

	printf("%d",ans);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;



int n,k,a,maxa,c[200001],ans;



int main(){

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

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

        scanf("%d",&a);

        if(a>maxa)maxa=a;

        c[a]++;

    }

    n=maxa;

    sort(&c[1],&c[n+1]);

    for(int i=1;i<=n-k;i++)ans+=c[i];

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

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define int long long

signed main() {

    #ifdef HOME

    freopen("input.txt", "r", stdin);

    #else

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

    #endif



    map <int, int> d;

    int n, k;

    cin >> n >> k;

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

        int x; cin >> x; ++d[x];

    }   

    vector <int> a;

    for (auto e : d) a.push_back(e.second);

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

    reverse(a.begin(), a.end());

    int ans = 0;

    while (a.size() > k) {

        ans += a.back();

        a.pop_back();

    }   

    cout << ans << '\n';

}   

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;



int n,k,a,maxa,c[200001],ans;



int main(){

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

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

        scanf("%d",&a);

        if(a>maxa)maxa=a;

        c[a]++;

    }

    n=maxa;

    sort(&c[1],&c[n+1]);

    for(int i=1;i<=n-k;i++)ans+=c[i];

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

    return 0;

}


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

#include<algorithm>

#include<iostream>

#include<iomanip>

#include<cstring>

#include<cstdlib>

#include<utility>

#include<string>

#include<cmath>

#include<cstdio>

#include<vector>

#include<bitset>

#include<ctime>

#include<queue>

#include<deque>

#include<stack>

#include<map>

#include<set>

using namespace std;

const int inf=2147483647,dx[]={-1,0,1,0},dy[]={0,-1,0,1};// ÉÏ ×ó ÏÂ ÓÒ

const int N=100005,M=1000005,mod=1000000007;

const long long llinf=9223372036854775807ll;

//int & long long

int n,k,t,a[200005],ans;

vector<int> v;

int main(){

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

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

	{

		scanf("%d",&t);

		a[t]++;

	}

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

		if(a[i]!=0)

			v.push_back(a[i]);

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

	if(v.size()<=k)

	{

		cout<<0;

		return 0;

	}

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

		ans+=v[i];

	cout<<ans;

	return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;



int n,k,a,maxa,c[200001],ans;



int main(){

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

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

        scanf("%d",&a);

        if(a>maxa)maxa=a;

        c[a]++;

    }

    n=maxa;

    sort(&c[1],&c[n+1]);

    for(int i=1;i<=n-k;i++)ans+=c[i];

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

    return 0;

}


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

#include <string>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <vector>

#include <cmath>

#include <algorithm>

#include <map>

#include <sstream>

#include <queue>

#include <deque>

#include <set>

#include <stack>

#include <functional>

#include <utility>

#include <stdio.h>

#define ll long long

#define MP make_pair

#define PII pair<int, int>

#define PLL pair<ll, ll>

#define PLI pair<ll, int>

#define PIL pair<int, ll>

#define F first

#define S second

#define SHN 1e9

#define LSHN 1e18

using namespace std;

map<int, int> mp;

int n,m;

int res=0;

vector<int> v;

int main()

{

	cin >>n>>m;

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

	{

		int x;

		cin >>x;

		mp[x-1]++;

	}

	if (mp.size()<=m)

	{

		cout <<"0";

		return 0;

	}

	for (map<int, int>::iterator it=mp.begin();it!=mp.end();it++)

	    v.push_back(it->second);

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

	for (int i=0;i<v.size()-m;i++) res+=v[i];

	cout <<res;

	return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;



int n,k,a,maxa,c[200001],ans;



int main(){

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

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

        scanf("%d",&a);

        if(a>maxa)maxa=a;

        c[a]++;

    }

    n=maxa;

    sort(&c[1],&c[n+1]);

    for(int i=1;i<=n-k;i++)ans+=c[i];

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

    return 0;

}


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

#include <cstdio>  

#include <cstring>  

#include <algorithm>  

using namespace std;  

const int maxn=2e5+100;  

int par[maxn],sum[maxn];  

int N,K,p,tot;  

void intt(int n)  

{  

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

        par[i]=i;  

}  

  

int find(int x)  

{  

    if(par[x]==x)  

        return x;  

    return par[x]=find(par[x]);  

}  

void unit(int x,int y)  

{  

    int fx=find(x),fy=find(y);  

    if(fx!=fy)  

        par[fx]=fy;  

}  

bool same(int x,int y)  

{  

    return find(x)==find(y);  

}  

int main()  

{  

    while(~scanf("%d%d",&N,&K))  

    {  

        int ans=0;  

        memset(sum,0,sizeof(sum));  

        memset(par,0,sizeof(par));  

        tot=0;  

        intt(N);  

        int t;  

        scanf("%d",&t);  

        sum[t]++;  

        p=t;  

        tot++;  

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

        {  

            scanf("%d",&t);  

            sum[t]++;  

            if(!same(t,p))  

            {  

                tot++;  

                unit(t,p);  

            }  

        }  

        sort(sum,sum+N+1);  

        if(tot<=K)  

            ans=0;  

        else  

        {  

            int cnt=tot-K;  

            int pos=lower_bound(sum,sum+N+1,1)-sum;  

            while(cnt--)  

                ans+=sum[pos++];         

        }  

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

    }  

    return 0;  

}  

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;



map<int, int> mp;

vector<int> v;



int main(){



    int n, k, a;

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

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

        scanf("%d", &a);

        ++mp[a];

    }



    int cnt=mp.size();

    if(cnt<=k)

        puts("0");

    else{

        long long ans=0LL;

        for(auto i:mp)

            v.push_back(i.second);

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

        int sz=cnt-k;

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

            ans+=(1LL*v[i]);



        printf("%d", ans);

    }













    return 0;

}


// Fastest known solution for this problem: