#define int long long

namespace IO {
    #define int long long 
    #define gh getchar
    inline int read(){char ch=gh();int x=0;bool t=0;while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();return t?-x:x;}
    inline char getc(){char ch=gh();while(ch<'a'||ch>'z') ch=gh();return ch;}
    inline void write(int x){if(x < 0){putchar('-');x = -x;}if(x > 9){write(x / 10);}putchar((x % 10 + '0'));}
}
using namespace IO;
using namespace std;
int a[1000100];
int cnt[1002010];
int vis[1002010];
int s[1002100];
signed main(){
    int n, k;
    cin >> n >> k;
    int o = 0;
    for(int i = 1; i <= n; i++)cin >> a[i];
    for(int i = 1; i <= n; i++){
        cnt[a[i]]++;if(cnt[a[i]] == 1)o++;
    }
    sort(cnt+1,cnt+1+n);
    int ans = 0;
    for(int i = 1; i <= n; i++)s[i] = s[i-1] + cnt[i];
    if(true){
        int p = upper_bound(cnt+1,cnt+1+n,k) - cnt;
        int lo = s[n] - s[p-1];
        // cout << p <<" "<< lo;
        if(lo<=k){
            printf("pigstd\n");
            return 0;
        }
    }
    for(int i = 1; i <= 1000010; i++)if(cnt[i]){
        int p = upper_bound(cnt+1,cnt+1+n,cnt[i]+k) - cnt;//cnt[p]大于cnt[i]+k
        int lo = n - s[p-1] - ((cnt[i]+k) * (n-p+1));
        if(lo <= k){
            ans++;
        }
    }
    if(ans > o)cout<<o;
    else cout << ans;
}

用的是二分考虑