#include "ricehub.h"
#include<bits/stdc++.h>
#define fi first
#define se second
//#define int long long
using namespace std;
using db=double;
using ll=int64_t;
using sll=__int128;
using lb=long double;
int besthub(int n, int m, int a[], long long mx){
#define int long long
vector<int>v(n+1); vector<int>prefix(n+1);
for(int i=0; i<n; i++){
v[i+1]=a[i]; prefix[i+1]=v[i+1]+prefix[i];
}
int ans=0; unordered_map<int,int>mp;
for(int i=1; i<=n; i++)mp[v[i]]++;
auto check=[&](int mid, int idx){
long long tot=0;
int lidx=lower_bound(v.begin()+1,v.end(),v[idx]-mid)-v.begin();
int ridx=upper_bound(v.begin()+1,v.end(),v[idx]+mid)-v.begin()-1;
if(lidx<idx){
tot+=v[idx]*(idx-lidx)-(prefix[idx-1]-prefix[lidx-1]);
}
if(ridx>idx){
tot+=(prefix[ridx]-prefix[idx])-v[idx]*(ridx-idx);
}
return tot;
};
for(int i=1; i<=n; i++){
int left=0; int right=v[n]-v[1]; int amt=mx;
while(left<right){
int mid=(left+right+1)>>1;
if(check(mid,i)<=mx)left=mid; else right=mid-1;
}
int lidx=lower_bound(v.begin()+1,v.end(),v[i]-left)-v.begin();
int ridx=upper_bound(v.begin()+1,v.end(),v[i]+left)-v.begin()-1;
if(lidx<i){
amt-=v[i]*(i-lidx)-(prefix[i-1]-prefix[lidx-1]);
}
if(ridx>i){
amt-=(prefix[ridx]-prefix[i])-v[i]*(ridx-i);
}
int l=1e18; int r=1e18; int cur=ridx-lidx+1;
if(lidx-1>0)l=abs(v[i]-v[lidx-1]);
if(ridx+1<=n)r=abs(v[i]-v[ridx+1]);
if(min(l,r)==1e18){
ans=max(ans,cur); continue;
}
if(l<r){
cur+=min((int)(amt/l),mp[v[lidx-1]]);
}else if(r<l){
cur+=min((int)(amt/r),mp[v[ridx+1]]);
}else if(r==l){
cur+=min((int)(amt/r),mp[v[ridx+1]]+mp[v[lidx-1]]);
}
ans=max(ans,cur);
}
#undef int
return ans;
}
